Распределение простых чисел

Когда OpenSSL генерирует RSA-2048 ключ, он ищет два случайных 1024-битных простых числа. Насколько долго? Теорема о простых числах отвечает точно: среди 1024-битных нечётных чисел каждое ~355-е простое. Случайный выбор плюс тест Миллера-Рабина - ключ за 10 мс. Без ТПЧ мы бы не знали: ждать миллисекунды или годы.

• **RSA генерация ключей:** ТПЧ → ~355 кандидатов на каждое 1024-битное простое; два простых → ~710 итераций
• **Хеш-таблицы:** размер выбирается простым числом; ТПЧ гарантирует ближайшее простое к N на расстоянии O(ln N)
• **Криптографические параметры:** safe prime p = 2q+1 - частота ≈ 1/(2·ln²(p)); генерация занимает дольше

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

• Квадратичные вычеты

Функция π(x) и подсчёт простых

Простые числа рассеяны среди натуральных как звёзды: кажется хаотично, но на больших масштабах обнаруживается строгий порядок. Функция π(x) - количество простых, не превышающих x - один из главных объектов изучения аналитической теории чисел.

**Функция π(x):** количество простых p ≤ x. Значения: - π(10) = 4: {2, 3, 5, 7} - π(100) = 25 - π(1000) = 168 - π(10⁶) = 78 498 - π(10⁹) ≈ 50 847 534 **Плотность:** доля простых среди {1,...,x} убывает как 1/ln x.

Для криптографии практически важно: среди случайных 1024-битных нечётных чисел примерно каждое ln(2¹⁰²⁴)/2 ≈ 355-е является простым. При генерации RSA-ключа нужно проверить порядка 355 кандидатов. Это быстро.

Теорема о простых числах

Главный результат о распределении простых - теорема о простых числах (ТПЧ), доказанная независимо Адамаром и де ла Валле Пуссеном в 1896 году. Она утверждает, что π(x) асимптотически ведёт себя как x/ln x.

**Теорема о простых числах (1896):** π(x) ~ x / ln x То есть lim_{x→∞} π(x) · ln(x) / x = 1. **Более точная оценка:** π(x) ~ Li(x) = ∫₂ˣ dt/ln t **Логарифмический интеграл Li(x):** - Li(10⁶) ≈ 78628, π(10⁶) = 78498 (ошибка 0.16%) - x/ln x при x=10⁶ ≈ 72382 (ошибка 7.8%) **Вероятность:** случайное n является простым с вероятностью ≈ 1/ln(n).

Быстрая оценка для криптографии: количество простых в [N, N+M] ≈ M/ln(N). Для N = 2¹⁰²⁴: ln(2¹⁰²⁴) = 1024·ln 2 ≈ 710. Среди нечётных кандидатов простота каждые ≈355 чисел.

Постулат Бертрана и гипотеза Римана

ТПЧ - асимптотический результат. Для конкретных вопросов нужны точные инструменты. Постулат Бертрана гарантирует существование простого в любом диапазоне [n, 2n]. Гипотеза Римана - ключ к точности π(x).

**Постулат Бертрана (теорема Чебышёва, 1852):** Для любого n > 1 существует простое p: n < p < 2n. **Следствие:** между x и 2x всегда есть простое. **Гипотеза Римана (1859, не доказана):** Все нетривиальные нули ζ(s) лежат на прямой Re(s) = 1/2. **Связь с π(x):** |π(x) − Li(x)| = O(√x · ln x) То есть Li(x) - «почти точное» значение π(x). **Статус:** Millennium Prize Problem ($1 000 000).

Гипотеза Римана остаётся нерешённой более 160 лет. Её доказательство дало бы точные оценки распределения простых и имело бы следствия для криптографии, теории случайных матриц и физики. Проверена для первых 10¹³ нулей.

Промежутки между простыми

Промежуток g(p) = pₙₑₓₜ − p между соседними простыми может быть как 2 (близнецы), так и сколь угодно большим. Для криптографии важно: случайно выбранные большие простые вряд ли будут «опасно близки» - но это нужно проверять.

**Промежутки между простыми:** - Средний промежуток вблизи x ≈ ln(x) - Простые-близнецы: g = 2 (гипотеза - не доказана) - Рекордные промежутки растут ~ (ln p)²/ln ln p - Теорема Жана (2013): бесконечно много пар с g ≤ 246 **Значение для криптографии:** - Атака Ферма на RSA: если |p − q| мало (p ≈ q ≈ √n), факторизация легкая - Нужно выбирать p и q так, чтобы |p − q| ≥ 2^(n/2 − 100) - Хеш-таблицы: ближайшее к N простое находится за O(log² N) проверок

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

• **π(x):** количество простых ≤ x; плотность простых вблизи x ≈ 1/ln x
• **ТПЧ:** π(x) ~ x/ln x (1896); Li(x) точнее; вероятность простоты числа n ≈ 1/ln n
• **Постулат Бертрана:** между n и 2n всегда есть простое - практически важно для поиска простых
• **Гипотеза Римана:** нули ζ(s) на Re=1/2; доказательство дало бы |π(x) − Li(x)| = O(√x ln x)

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

Распределение простых связывает аналитическую теорию с криптографическими приложениями:

• Тесты простоты — ТПЧ определяет число кандидатов; тесты Миллера-Рабина проверяют каждый кандидат
• Аналитическая теория чисел — Функция Чебышёва θ(x) и дзета-функция Римана - инструменты доказательства ТПЧ
• Числа в криптографии — Частота простых определяет скорость и безопасность генерации RSA-параметров

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

• Если бы простые числа были равномерно распределены с плотностью 1/ln x, изменилась бы практика генерации RSA-ключей?
• Гипотеза Римана связана с нулями ζ(s). Что произойдёт с криптографическими оценками, если её докажут или опровергнут?
• Почему промежутки между простыми важны для атаки Ферма на RSA? Что значит «p и q близки» в контексте факторизации?

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

• calc-03-limits-intro