Механический отбор и первые попытки построить полиномы

Древнегреческие математики осознавали фундаментальную роль простых чисел как неделимых кирпичиков арифметики. В третьем веке до нашей эры Эратосфен Киренский предложил алгоритмический способ их нахождения. Метод заключался в последовательном вычеркивании составных чисел из числового ряда. Это рабочий алгоритм, но он требует хранения огромных массивов данных в памяти и крайне медленно продвигается по числовой прямой.

В эпоху Возрождения и Нового времени исследователи стремились выразить простые числа явной алгебраической формулой вида f(n). Пьер де Ферма в 1640 году предположил, что числа вида 2^(2^n) + 1 всегда простые. Для n от нуля до четырех формула действительно давала простые значения: 3, 5, 17, 257 и 65537. Гипотеза казалась безупречной, пока Леонард Эйлер в 1732 году не проверил следующее значение при n равном пяти. Число 4294967297 оказалось составным и разделилось на 641.

Сам Эйлер в 1772 году обнаружил квадратичный многочлен f(n) = n^2 + n + 41. При подстановке целых чисел от нуля до 39 этот полином выдает непрерывную серию из сорока простых чисел. На сороковом шаге получается составное число, равное квадрату сорока одного. Позже Карл Фридрих Гаусс доказал строгое алгебраическое ограничение. Ни один непостоянный многочлен с целыми коэффициентами от одной переменной не способен порождать исключительно простые числа при любых натуральных значениях аргумента.

Аналитический сдвиг Гаусса и закон распределения

Осознав тупиковость поиска элементарного алгебраического генератора, математики изменили угол зрения. Вместо угадывания каждого отдельного числа они начали изучать их плотность на больших отрезках. Юный Гаусс в конце восемнадцатого века изучал таблицы простых чисел и заметил закономерность. Доля простых чисел среди первых N натуральных чисел ведет себя обратно пропорционально натуральному логарифму N.

Функция распределения простых чисел pi(x), обозначающая их количество до заданной границы x, асимптотически приближается к интегральному логарифму li(x). Точное доказательство этой теоремы о распределении простых чисел появилось лишь в 1896 году благодаря независимым работам Жака Адамара и Шарля Жана де ла Валле-Пуссена. Они показали, что отношение pi(x) к величине x / ln(x) стремится к единице при росте x до бесконечности.

Дзета-функция и гипотеза Римана

Настоящий прорыв в понимании природы простых чисел совершил Бернхард Риман в 1859 году. Он опубликовал короткую восьмистраничную работу, где связал дискретный мир простых чисел с непрерывным миром комплексного анализа. Риман исследовал дзета-функцию, введенную еще Эйлером для вещественных значений, и распространил ее на всю комплексную плоскость.

Эйлер установил тождество, связывающее бесконечную сумму степеней натуральных чисел с бесконечным произведением по всем простым числам. Риман показал, что распределение простых чисел строго контролируется нулями этой дзета-функции в комплексной плоскости. Неточные колебания вокруг гладкой функции интегрального логарифма описываются гармониками, частоты которых задаются мнимыми частями нетривиальных нулей.

Гипотеза Римана утверждает, что все нетривиальные нули дзета-функции лежат строго на критической прямой с вещественной частью одна вторая. Если это предположение верно, отклонение реального количества простых чисел от предсказанной формулы имеет минимально возможную случайную погрешность порядка корня из x умноженного на логарифм x. Эта гипотеза остается нерешенной до сих пор.

Существующие формулы и их скрытая бесполезность

В двадцатом веке математики все же построили точные формулы для n-го простого числа, однако практического смысла они не имеют. В 1947 году Уильям Миллс доказал существование константы A, при которой округление вниз выражения A^(3^n) всегда выдает простое число при любом натуральном n. Константа Миллса иррациональна, и для ее вычисления необходимо заранее знать сами эти простые числа с чудовищной точностью.

В 1971 году математик К. П. Уилланс сконструировал точную явную аналитическую формулу для n-го простого числа, основанную на теореме Вильсона. Выражение использует тригонометрические функции и вложенные суммы факториалов. Чтобы вычислить десятое простое число по этой формуле, компьютеру приходится выполнять астрономическое число операций над факториалами огромных чисел. Алгоритмическая сложность такого расчета экспоненциальна.

Еще один поразительный результат получили в 1976 году Джеймс Джонс, Дайсуке Сато, Хайдо Вада и Питер Винес. Опираясь на решение десятой проблемы Гильберта Юрием Матиясевичем, они построили диофантов многочлен от 26 переменных степени 25. Множество положительных значений этого многочлена при подстановке неотрицательных целых чисел в точности совпадает со множеством всех простых чисел. Подавляющее большинство комбинаций переменных выдает отрицательные числа, а алгоритмический перебор для получения нового простого числа работает медленнее прямого деления столбиком.

Современное состояние проблемы

Сегодня фокус внимания теоретиков сместился к интервалам между соседними простыми числами. В 2013 году Итан Чжан доказал наличие бесконечного числа пар простых чисел с разницей меньше семидесяти миллионов. В рамках совместного сетевого проекта Polymath и благодаря работам Джеймса Мейнарда эту границу удалось опустить до 246. Математики продолжают приближаться к доказательству знаменитой гипотезы о простых числах-близнецах, расстояние между которыми равно двум.

Простые числа ведут себя детерминированно в локальных масштабах и псевдослучайно на бесконечных интервалах. Отсутствие удобной формулы перестало восприниматься как трагедия анализа. Вместо нее математики получили мощный аппарат теории вероятностей, комплексного анализа и спектральной теории случайных матриц, описывающий простые числа глубже любых элементарных формул.

Частые вопросы

Почему нельзя использовать решето Эратосфена для современных криптографических ключей?

Решето Эратосфена требует последовательного прохода по всей числовой прямой от двойки до нужного числа. В криптографии используются простые числа длиной в сотни или тысячи бит. Размер числовой прямой для таких чисел превышает количество атомов в наблюдаемой Вселенной, поэтому алгоритм физически невозможно завершить за разумное время.

Что такое числа Мерсенна и помогают ли они искать простые числа?

Числа Мерсенна имеют вид 2^p - 1, где показатель степени p сам является простым числом. Для проверки их простоты существует специализированный и очень быстрый тест Люка — Лемера. Именно благодаря этой специфической форме крупнейшие известные на сегодня простые числа находят среди чисел Мерсенна в рамках распределенного вычислительного проекта GIMPS.

Как компьютеры находят простые числа без точной формулы?

Вместо точных формул компьютеры генерируют случайное большое нечетное число и тестируют его на простоту. Для этого применяют полиномиальные вероятностные алгоритмы, такие как тест Миллера — Рабина. Если число проходит несколько десятков раундов теста, вероятность ошибки становится пренебрежимо малой, стремясь к нулю.

Что произойдет, если кто-то докажет гипотезу Римана?

Доказательство гипотезы Римана подтвердит сильнейшую оценку погрешности для асимптотического закона распределения простых чисел. Это мгновенно решит сотни математических теорем, которые сейчас сформулированы с оговоркой об истинности гипотезы Римана, но не разрушит интернет-шифрование одномоментно.