Аналитическая теория чисел (обзор)

«Мёртвая» математика XIX века неожиданно оказалась живой. Дзета-функция Римана - уравнение на бумаге 1859 года - управляет распределением простых чисел в XXI веке. Нули ζ(s) определяют, насколько точно Li(x) приближает π(x), а это напрямую влияет на криптографические оценки RSA-параметров. Каждое HTTPS-соединение - косвенный потомок работы Римана.

• **RSA параметры:** оценки безопасности ключей основаны на ТПЧ; если бы гипотеза Римана была нарушена, некоторые оценки пришлось бы пересматривать
• **Простые в прогрессиях:** safe primes p=2q+1 гарантированно бесконечны (Дирихле); это обоснование для DH и DSA параметров
• **Методы просева:** квадратичное решето и GNFS - алгоритмы факторизации, использующие аналитические оценки плотности гладких чисел

Предварительные знания

• Algebraic Number Theory: An Overview

Дзета-функция Римана и произведение Эйлера

Эйлер в 1737 году открыл удивительную формулу, связывающую сумму по всем натуральным числам с произведением по всем простым - своеобразная «Суперпозиция» арифметики. Риман в 1859 году расширил её на комплексную плоскость и обнаружил глубокую связь с распределением простых.

**Дзета-функция Римана:** ζ(s) = Σₙ₌₁^∞ 1/nˢ = 1 + 1/2ˢ + 1/3ˢ + ... **Произведение Эйлера:** ζ(s) = ∏_p (1 − p⁻ˢ)⁻¹ (произведение по всем простым p) **Особые значения:** - ζ(2) = π²/6 ≈ 1.645 (Базельская задача, Эйлер 1734) - ζ(4) = π⁴/90 - ζ(−1) = −1/12 (в смысле аналитического продолжения) **Связь с ТПЧ:** нули ζ(s) в полосе 0 < Re(s) < 1 управляют ошибкой в π(x) ~ Li(x).

Произведение Эйлера ζ(s) = ∏(1−p⁻ˢ)⁻¹ - аналитическое воплощение основной теоремы арифметики. Расширение каждого множителя в геометрический ряд и перемножение даёт ровно одно слагаемое для каждого натурального числа - в силу единственности разложения на простые.

Символы Дирихле и L-функции

Дирихле в 1837 году доказал: в любой арифметической прогрессии a, a+d, a+2d, ... (при gcd(a,d)=1) бесконечно много простых. Доказательство использует L-функции - «цветные версии» дзета-функции, отслеживающие простые в отдельных классах вычетов.

**Символ Дирихле χ mod q:** мультипликативная функция χ: ℤ → ℂ с χ(n+q) = χ(n) и χ(n)=0 при gcd(n,q)>1. **L-функция Дирихле:** L(s, χ) = Σ χ(n)/nˢ = ∏_p (1 − χ(p)·p⁻ˢ)⁻¹ **Теорема Дирихле:** для gcd(a,q)=1 существует бесконечно много простых p ≡ a (mod q). **Доказательство:** L(1, χ) ≠ 0 и ∞ для любого не-главного χ → все классы равноценны. **Применение:** распределение простых по классам вычетов; «prime number theorem for arithmetic progressions».

Теорема Дирихле о простых в прогрессиях говорит: «места есть для всех». Для криптографии это значит: при поиске простых вида p ≡ 3 (mod 4) (нужных для теста Тонелли-Шенкса) или p = 2q+1 (safe primes) можно быть уверены в их бесконечной доступности.

Функции Чебышёва и путь к ТПЧ

Чебышёв в 1850 году ввёл функции θ(x) и ψ(x), которые оказались более удобными для анализа, чем π(x). Через них был проложен путь к строгому доказательству теоремы о простых числах.

**Функции Чебышёва:** θ(x) = Σ_{p≤x} ln p (сумма логарифмов простых ≤ x) ψ(x) = Σ_{pᵏ≤x} ln p (сумма логарифмов «прямых» простых и их степеней) **Связи:** - ψ(x) = θ(x) + O(√x · ln x) - θ(x) ~ x ⟺ ψ(x) ~ x ⟺ π(x) ~ x/ln x (ТПЧ) **Чебышёв доказал:** 0.92 · x/ln x < π(x) < 1.11 · x/ln x (1850, до полного ТПЧ). **Связь с нулями ζ:** явная формула ψ(x) = x − Σ_ρ x^ρ/ρ − ln(2π) − 1/2 · ln(1−x⁻²)

Функции Чебышёва θ(x) и ψ(x) технически проще для анализа через ζ(s), чем π(x). Связь ψ(x) ↔ нули ζ(s) через явную формулу - ключевой мост аналитической теории чисел.

Ключевые идеи

• **ζ(s) = ∏(1−p⁻ˢ)⁻¹:** произведение Эйлера - аналитическое воплощение ФТА; нули управляют π(x)
• **L(s, χ):** L-функции Дирихле обобщают ζ(s) на классы вычетов; L(1,χ)≠0 → теорема о простых в прогрессиях
• **θ(x), ψ(x):** функции Чебышёва; θ(x)/x → 1 эквивалентно ТПЧ; технически удобнее π(x) для анализа
• **Явная формула:** ψ(x) = x − Σ_ρ x^ρ/ρ − ...; нули ρ ζ(s) - «частоты колебаний» π(x) вокруг Li(x)

Связанные темы

Аналитическая теория чисел - вершина математической структуры этого курса:

• Распределение простых — ТПЧ - главный результат аналитической теории; ζ(s) - её инструмент
• Алгебраическая теория чисел — Дзета-функции Дедекинда обобщают ζ(s) на числовые поля; их нули управляют распределением идеалов
• Числа в криптографии — Оценки RSA, DH и анализ атак факторизацией используют аналитические результаты

Вопросы для размышления

• Произведение Эйлера ζ(s) = ∏(1−p⁻ˢ)⁻¹ сходится для Re(s) > 1. Что происходит при s → 1+? Как это связано с бесконечностью множества простых?
• Явная формула ψ(x) = x − Σ_ρ xᵖ/ρ − ... содержит сумму по нулям ζ. Почему гипотеза Римана (нули на Re=1/2) даёт наилучшую оценку остатка?
• L-функции Дирихле отслеживают простые в конкретных классах вычетов. Как это связано с выбором параметров для DH (safe primes, Sophie Germain primes)?

Связанные уроки

• calc-03-limits-intro