Большие простые числа: теория и практика их поиска
Антон Фролов «Функция Эйлера»
Самое большое простое число, известное на данный момент, состоит из почти 25 млн. цифр. Есть ли простые числа больше? Несомненно. Простых чисел бесконечное количество. Найдём ли мы простое число больше 25 млн. цифр? Тоже да, поиск не останавливается ни на секунду. Можно ли принять в нём участие? Конечно, достаточно присоединиться к одному из добровольных распределённых проектов по поиску больших простых чисел.
Но сначала вспомним, что такое простое число. Это число, которое делится без остатка только на само себя и на единицу. Самое маленькое простое число это 2, за ним идут 3, 5, 7, 11, 13, 17, и этот список можно продолжать бесконечно. Чем интересны такие числа? Тем, что все остальные числа состоят из них. Простые числа — это атомы, на которые можно разложить все другие, то есть составные числа. Такое разложение похоже на химическую формулу (один атом может входить в неё несколько раз), и оно уникально для каждого составного числа. Например, число 12 раскладывается как 12 = 22·3. Конечно, можно записать 12 = 2·6, но 6 не является простым числом, а значит после дальнейшего разложения получится 12 = 2·2·3.
Но если простых чисел бесконечное количество, то зачем искать самое большое? Потому что мы можем. Всё дело в присущих человеку любопытстве и азарте первооткрывателя. Когда‑то поиск простых чисел был трудоёмким процессом, требующим большого количества бумаги и времени. Но и результат мог оказаться впечатляющим. Например, великий российский математик швейцарского происхождения Леонард Эйлер доказал простоту числа 231–1, и это было самое большое известное простое число в течение почти ста лет. С появлением же электронных вычислительных машин, прогресс резко ускорился. Математики находили всё бóльшие простые числа, задумывались об эффективности расчётов, придумывали новые алгоритмы, которые позволяли находить ещё бóльшие простые числа на тех же самых вычислительных машинах. Сначала количество цифр в самом большом простом числе измерялось сотнями, потом тысячами, потом миллионами.
К настоящему времени, потребность в вычислительных ресурсах для продолжения поиска настолько велика, что превышает возможности отдельных энтузиастов. Так как эта задача не сулит никакой экономической или политической выгоды, то и заинтересованности со стороны коммерческих или государственных структур нет. Поэтому люди начали объединяться в сообщества добровольных распределённых вычислений, такие как GIMPS и PrimeGrid. Для вступления в такое сообщество не нужно обладать какими‑то специальными знаниями, достаточно иметь производительный компьютер и желание потратить его мощность на поиск простых чисел. Всё необходимое программное обеспечение будет вам предоставлено.
Кстати, программное обеспечение используется весьма специфическое. Оно заточено на извлечение максимальной производительности из современных компьютеров, задействует все возможные блоки процессоров и видеокарт, вызывает максимальную нагрузку на все компоненты. Иногда его даже используют для стресс‑тестов вновь собранных компьютеров. Как шутят разработчики: «Наш софт расплавит ваш ноутбук и взорвёт ваш блок питания!» Вычислительное ядро написано с использованием самых новых наборов инструкций процессоров, но при этом постоянно используются различные математические хитрости, ускоряющие вычисление конкретных математических операций. Но расплатой за такую эффективность является крайне узкая специализация — это программное обеспечение практически невозможно применять ни для чего другого, кроме поиска очень больших простых чисел. Кроме того, крайне не рекомендуется пытаться писать собственные программы, во всяком случае не изучив сначала теорию операций над большими числами (изложенную, например, в этом трактате).
В сообществе разработкой программного обеспечения занимается всего несколько человек. Также, в сообществе есть несколько математиков, которые иногда подкидывают идеи вида: «А давайте поищем среди чисел вот такой формы числа, обладающие вот таким свойством?» Если предложение заинтересует сообщество, то в дело вступают администраторы и разработчики бекенда, организующие систематический поиск и подтверждение результатов. Как правило, результатом является нахождение какого‑нибудь простого числа, которое тут же регистрируется на сайте T5K.org, ведущем независимый учёт и проверку простых чисел.
Если зайти на этот сайт и посмотреть на Top 20 простых чисел, то можно заметить, что там доминируют числа вида 2n-1. Такие числа называются числами Мерсенна, и их поиском занимается сообщество GIMPS. Самое большое известное простое число является числом Мерсенна. Но не только благодаря успешности GIMPS, но ещё и благодаря существованию самых эффективных алгоритмов, заточенных исключительно под эту форму и реализованных как на процессорах, так и на видеокартах. Сообщество PrimeGrid занимается числами других форм, алгоритмы работы с которыми не такие эффективные и не подходят по ряду параметров для реализации на видеокартах. Но зато PrimeGrid работает над доказательством некоторых математических гипотез, например, над задачей отыскания минимального числа Серпинского. Работа PrimeGrid разбита на несколько подпроектов, и у тех, что связаны с математическими гипотезами, есть конкретная цель, после достижения которой подпроект будет закрыт. Кроме того, на PrimeGrid существуют подпроекты по поиску относительно небольших простых чисел длиной около 600 тыс. цифр. Найти такое число не составляет труда, современный домашний компьютер справится с этой задачей за несколько месяцев (если повезёт) или за год (если не повезёт). Это позволяет новичкам втянуться, почувствовать азарт и гордость от того, что вписал своё имя в список T5K.org, хоть и под номером 4900 в Top 5000.
Интересной особенностью простых чисел является их распределение, очень похожее на распределение случайных чисел. В практическом плане это означает, что каждое большое число может оказаться простым с некоторой вероятностью. Так это или нет можно узнать только проверив, но эта проверка и является самым ресурсозатратным действием. Проверка одного большого числа на простоту может занимать от часа до недели, в зависимости от размера числа и мощности вашего устройства. При этом, всегда есть шанс, что по результату проверки окажется, что число простое. Эта особенность делает поиск больших простых чисел похожим на рыбалку. Вы можете поймать огромную рыбу через 5 минут после закидывания снасти, а можете не поймать ничего и за месяц. Из‑за этого сообщества GIMPS и PrimeGrid иногда напоминают сообщества рыбаков, обсуждающих свои снасти (компьютерное железо), места, где хорошо клюёт (оптимальные подпроекты), и повадки рыбы (математическую теорию). Кроме того, вклад каждого участника учитывается, он получает очки, на основании которых формируются рейтинги и раздаются нарисованные медальки. Всё это делает процесс поиска весёлым и превращает его в полноценное хобби. Известны случаи, когда энтузиасты строили дата‑центры у себя в гараже для поиска простых чисел.
Процессор, обнаруживший простое число из Top 20.
Как непосредственно организован процесс поиска? Прежде всего, выбирается форма числа, то есть выбирается формула с одной переменной, например 2n-1. Эта формула даёт нам последовательность, в которой каждое отдельное число называется «кандидат». На этом этапе нужно быть очень осторожным, поскольку для некоторых формул может существовать алгебраическое разложение, то есть ни один кандидат не будет простым. Например, 22n-1=(2n-1)·(2n+1). Необходима консультация с математиком, чтобы он подтвердил, что алгебраического разложения нет. Иначе можно потратить годы на изначально обречённые поиски. Известно, что число Мерсенна может быть простым только тогда, когда показатель степени сам простой, иначе существует алгебраическое разложение. Чтобы подчеркнуть этот факт, простые числа Мерсенна обозначают формулой 2p-1. Таким образом, мы сразу же отметаем огромное количество кандидатов.
Но мы можем исключить ещё множество кандидатов. Греческий математик Эратосфен известен тем, что довольно точно вычислил диаметр Земли в 240 году до нашей эры. Но кроме этого он придумал алгоритм нахождения всех простых чисел, заключающийся в исключении кандидатов. Сначала вычёркиваются все кандидаты, делящиеся на 2, потом делящиеся на 3, потом делящиеся на 5 и так далее по списку маленьких простых. Этот алгоритм называется «решето Эратосфена», а процесс — «просеивание». В зависимости от формы наших кандидатов, просеивание может осуществляться очень быстро, даже без вычисления самого значения кандидата, а только по его формуле. Просеивание продолжается до тех пор, пока на исключение очередного кандидата не начнёт тратиться больше времени, чем на непосредственно тест простоты. В реальных проектах глубина просеивания (то есть, размер маленьких простых) превышает 1015. В случае, если делители кандидатов сами обязаны иметь определённую форму, глубина просеивания может достигать 1020. Например, числам Мерсенна опять повезло, их делители имеют вид 2·p·k+1 (211–1 = (2·11·1+1)·(2·11·4+1)), что позволяет при просеивании перебирать только k. Благодаря всем этим ухищрениям, от первоначального списка кандидатов остаётся лишь малая часть.
Существует много разных тестов простоты, работающих с разной скоростью. Количество операций с большими числами, необходимых для выполнения теста, зависит от длины числа в битах. У самых простых тестов эта зависимость линейная, сколько битов, столько и операций. На самом деле, на этих тестах можно и остановиться, потому что мы работаем с числами длиной от миллиона до 100 миллионов бит. Полиномиальные тесты простоты даже со степенью 2, даже со степенью 1,5 становятся неприменимы на практике. Если на выполнение 100 миллионов операций уходит день, то ждать 100 миллионов дней уже становится непрактично. Поэтому самым популярным тестом для поиска больших простых чисел является тест Фермá. Особенностью этого теста является то, что он всегда выявляет простые числа, но иногда может назвать хитрое составное число простым. Вероятность такого события для больших чисел исчезающе мала, но она есть. Поэтому в англоязычном сообществе этот тест часто называют PRP (от «probable prime»). Тем не менее, этот тест очень удобно использовать для распределённого поиска, потому что для него существуют надёжные алгоритмы защиты от ошибок и алгоритмы сертификации результата, что важно в открытых сообществах. Однако, сайт T5K.org не принимает числа, простота которых не является доказанной. Поэтому для каждого найденного вероятного простого числа следующим этапом нужно выполнять настоящий, детерминированный тест. О видах этих тестов поговорим в следующий раз.
Что такое поиск больших простых чисел? Это хобби, не имеющее практического применения (во всяком случае, в ближайшие тысячу лет), но обогащающее знаниями и практическим опытом. Это сообщество энтузиастов, разбросанных по всему земному шару. Это несколько человек, разрабатывающих невероятно сложный софт в свободное время. Это тайны мироздания, к которым может прикоснуться каждый. Это способ оставить свой след в вечности.
