Самое большое простое число: что это такое и зачем его ищут

Например, 7 можно разделить без остатка только на 1 и 7, поэтому оно простое. Если у числа есть другие делители, оно называется составным. Так, 6 делится не только на 1 и 6, но и на 2 и 3, а 9 можно представить как 3 × 3. Первые простые числа — 2, 3, 5, 7, 11, 13.

Из простых множителей можно получить любое натуральное число больше 1. Например, 6 = 2 × 3, а 12 = 2 × 2 × 3. Поэтому простые числа можно сравнить с деталями конструктора, из которых складываются составные. Причём набор таких «деталей» для каждого составного числа всегда один и тот же: 12 можно записать как 2 × 2 × 3 или 3 × 2 × 2, но множители останутся теми же.

У неё только один делитель — 1, а у простого числа их должно быть два. Составным оно тоже быть не может: единицу нельзя разложить на простые множители.

Если нужно найти сразу много простых чисел, используют решето Эратосфена. Их выписывают по порядку и начинают «просеивать»: сначала вычёркивают кратные 2, затем кратные 3 и так далее. После такого просеивания остаются простые числа.

Это доказал ещё древнегреческий математик Евклид.

Представим, что мы составили полный список всех простых чисел. Перемножим их и прибавим 1. Получившееся число не сможет разделиться без остатка ни на одно простое число из нашего списка. Значит, оно либо само простое, либо делится на другое простое число, которого в списке нет. Получается противоречие: список, который мы считали полным, на самом деле неполный. Следовательно, последнего простого числа не существует. Для этой теоремы известно не менее двухсот разных доказательств.

Поэтому у математиков не может быть окончательного рекорда: можно найти только крупнейшее простое число, известное на данный момент. По мере роста чисел простые встречаются в среднем всё реже, но никогда не заканчиваются.

Чтобы найти рекордно большое простое число, математики не перебирают подряд все возможные варианты. Вместо этого они используют числа Мерсенна — среди них удобно искать простые. Их получают по формуле 2ⁿ − 1: двойку возводят в степень и вычитают единицу.

Возьмём простые показатели степени:

2² − 1 = 3 — простое.

2³ − 1 = 7 — тоже простое.

2⁵ − 1 = 31 — снова простое.

Может показаться, что достаточно брать простой показатель степени и каждый раз получать простое число. Но это не так. Например:

2¹¹ − 1 = 2047.

Хотя 11 — простое, результат оказался составным: 2047 = 23 × 89.

Поэтому простой показатель степени — только первое условие для поиска. Если показатель составной, число Мерсенна не может быть простым. Если же показатель простой, появляется подходящий кандидат, который ещё нужно проверить.

Для этого существует специальный тест Лукаса — Лемера. Он подходит для чисел вида 2ᵖ − 1, где p — простое число больше 2. Проверка состоит из цепочки вычислений: результат одного шага используется в следующем. После последнего шага смотрят на получившийся остаток.

То есть тест даёт точный ответ.

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

Проверка огромных чисел требует много вычислений, поэтому эту работу можно разделить между множеством компьютеров. Именно так устроен GIMPS (Great Internet Mersenne Prime Search) — международный проект, который с 1996 года ищет простые числа Мерсенна.

К GIMPS могут подключаться владельцы обычных компьютеров. Система PrimeNet выдаёт каждому устройству небольшую часть общей работы: компьютер получает число для проверки, выполняет вычисления и отправляет результат обратно. В результате множество компьютеров выполняют разные задания, но вместе работают над одной большой задачей — поиском новых простых чисел Мерсенна.

Объём вычислений огромен. GIMPS проверяет числа Мерсенна со всё большими показателями степени.

Поиск нового простого числа может продолжаться годами, потому что кандидатов очень много и каждый нужно проверить. Если один из них оказывается простым, результат дополнительно проверяют на других устройствах и с помощью других программ. Только после подтверждения GIMPS объявляет об открытии.

GIMPS проверяет огромное количество чисел Мерсенна. Чтобы не тратить много времени на сложную проверку каждого кандидата, поиск проходит поэтапно.

1. Отсеивают составные числа. Сначала программа пытается найти у кандидата делитель. Если он находится, число точно составное и дальше его проверять не нужно.
2. Проверяют оставшихся кандидатов. Для этого GIMPS преимущественно использует PRP-тест. PRP означает probable prime — «вероятно простое». Если число проходит такой тест, оно может быть простым, но окончательного доказательства ещё нет. Вместе с тестом создаётся специальный proof-файл, который позволяет проверить, правильно ли были выполнены вычисления. Такой способ стал основным для поиска в GIMPS с 2020 года. А с 2021 года тест Лукаса — Лемера перестали использовать для первой проверки всех кандидатов.
3. Подтверждают возможное открытие. Если кандидат проходит PRP-тест и может оказаться новым простым числом, результат проверяют независимыми вычислениями. Для этого используют тест Лукаса — Лемера, который уже позволяет точно установить, простое это число или составное.

Таким образом, на каждом этапе кандидатов становится меньше, а самые сложные проверки проводят только для тех чисел, которые прошли предыдущие этапы. Но сами числа огромны и кандидатов много, поэтому поиск нового рекорда может продолжаться годами.

Это число Мерсенна, полученное по той же формуле, о которой шла речь выше, только показатель степени здесь огромный — 136 279 841.

Само число состоит из 41 024 320 десятичных цифр. Записать его целиком в статье практически невозможно, поэтому такие огромные числа обозначают формулой. Это 52-е известное простое число Мерсенна.

Его обнаружил 12 октября 2024 года участник проекта GIMPS Люк Дюран. Для поиска он использовал сеть облачных графических процессоров. Один из первых результатов был получен на NVIDIA A100, а затем его проверили тестом Лукаса — Лемера на NVIDIA H100.

На этом проверка не закончилась. Результат независимо подтвердили на разных аппаратных платформах и с помощью разных программ. Проверки завершились 19 октября 2024 года, а 21 октября GIMPS официально объявил об открытии. Но это не самое большое простое число вообще, а только самое большое из известных сейчас. Как мы уже выяснили, простых чисел бесконечно много, поэтому любой такой рекорд однажды может быть побит.

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

Представить эту идею можно с помощью замка. Закрыть замок ключом легко, а открыть его без ключа гораздо сложнее. Похожая ситуация возникает в RSA: перемножить два известных простых множителя легко, а по полученному огромному результату восстановить их на практике крайне трудно. С этой сложностью связана безопасность RSA. Если бы появился быстрый общий способ такого разложения, RSA-ключи стали бы небезопасными.

Однако современная криптография не ограничивается RSA. Для защиты данных применяют и другие математические методы, а из-за развития квантовых компьютеров уже идёт переход к постквантовой криптографии.

При этом рекорды для RSA не нужны: на практике используют гораздо меньшие значения. Поэтому открытие GIMPS из 41 024 320 цифр не служит криптографическим ключом. Такие гиганты ищут прежде всего для математических исследований.

Для небольшой величины специальные программы не нужны. Например, возьмём 97. Делить его на всё подряд не придётся: достаточно проверить простые делители до √97. Корень из 97 немного меньше 10, поэтому подходят только 2, 3, 5 и 7. На них 97 без остатка не делится, значит, 97 — простое число.

Если подходящего делителя нет, оно простое. А для поиска рекордных простых уже используют специальные программы и распределённые проекты — например, GIMPS, о котором мы рассказали выше.

Простых чисел бесконечно много, поэтому абсолютного рекорда среди них не существует — есть только крупнейшее известное на данный момент. На начало сентября 2026 года это число Мерсенна 2¹³⁶²⁷⁹⁸⁴¹ − 1, в записи которого 41 024 320 цифр.

Математики продолжают изучать, как устроены и распределены простые числа, а участники GIMPS ищут новых рекордсменов. Такие гиганты почти не нужны в повседневных вычислениях, но играют важную роль в математических исследованиях. Поэтому нынешний рекорд наверняка не последний.