В предыдущей статье я рассказал об общих принципах поиска больших простых чисел. Но как бы ни был организован поиск, в конце он всегда заканчивается тестом простоты. И, к сожалению, иногда случается ситуация, когда простое число-то мы нашли, но доказать его простоту не можем. Например, так получилось с самым маленьким простым числом из миллиона цифр 10⁹⁹⁹⁹⁹⁹+593499. Поэтому тестам простоты уделяется довольно много внимания в сообществах добровольных распределённых вычислений, таких как GIMPS и PrimeGrid.

Напомню, что при поиске простых чисел используется тест простоты Фермá. Это самый простой и надёжный тест, его можно применять к любым числам, и для него разработаны надёжные алгоритмы детекции ошибок и сертификации результатов. Но у этого теста есть особенность — он иногда даёт ложноположительный результат. Существуют особые составные числа, такие как числа Кармайкла, которые проходят тест Ферма. Вероятность встретить такое число невероятно низка, если бы такое число нашлось в одном из проектов распределённых вычислений, то это было бы событием куда более ярким, чем нахождение собственно большого простого числа. Тем не менее, сама теоретическая возможность того, что прошедшее тест Ферма число является составным, заставляет называть его «вероятно простым» (probable prime, PRP).

10⁹⁹⁹⁹⁹⁹+593499 является вероятно простым числом. Чтобы гарантированно доказать простоту, нужно провести "истинный" или "детерминированный" тест, который уберёт все вероятности, развеет сомнения и поставит точку. Однако, большинство таких тестов, доказывающих простоту произвольных чисел, оказались слишком медленными на практике, их можно применять к числам не длиннее нескольких тысяч цифр. На данный момент, самым эффективным из таких тестов является ECPP (Elliptic Curve Primality Proof) — алгоритм доказательства простоты с помощью эллиптических кривых. Его основной идей является использование специально сконструированных эллиптических кривых для рекурсивного сведения доказательства к простому числу немного меньшего размера.

Допустим, требуется доказать простоту числа N. С помощью сложного математического аппарата конструируется число M, которое лишь незначительно отличается от N. Однако, если у числа M существует простой делитель, по длине превышающий половину длины M, то это докажет простоту N (через всё те же сложные построения эллиптических кривых). В общем случае, задача разложения числа M на простые является гораздо более трудной, чем доказательство простоты. Однако, вероятность существования большого делителя линейна. Например, для чисел из 1000 цифр вероятность делителя из >900 цифр примерно равна 1-900/1000. То есть, у каждого десятого числа из 1000 цифр есть делитель из 900+ цифр. Также, нам может помочь самое приятное свойство эллиптических кривых — то, что мы можем сконструировать сколь угодно много кривых, и у каждой будет своё собственное M. Таким образом, алгоритм становится следующим: конструируем очередное M, убираем из него маленькие делители, проводим тест Ферма оставшейся части, и если он положительный, то вызываем рекурсивно этот же алгоритм на этом вероятно простом числе. Каждый шаг такого алгоритма будет уменьшать размер числа на 30-50 цифр. Более того, если вдруг возникнут трудности на каком-то шаге, можно вернуться на уровень выше и попробовать другое значение M. Работа этого алгоритма похожа на поиск пути в дереве с корнем в исходном большом числе и ветвями, тянущимися к маленьким числам из 1000 цифр, простоту которых легко доказать "обычными" тестами.

Если посмотреть на Top 20 простых чисел, доказанных с помощью ECPP, то у самого большого окажется всего 86 453 цифры. Это неудивительно, ведь на доказательство простоты одного такого числа могут уйти годы. К счастью, проверить это доказательство не занимает столько времени — повторно пройти по уже найденному пути несложно.

Но как же простые числа из миллионов и десятков миллионов цифр, которые мы видим в общем списке? ECPP неприменим для них, поскольку после 100 000 цифр время его работы становится запредельным. Однако, благодаря особой форме этих чисел, заканчивающихся на +1 и −1, для них были разработаны специализированные тесты. В основе этих тестов лежит использование специальных множеств, называемых «конечные группы». Такое множество содержит конечное число элементов (ими могут быть числа, координаты, что-то ещё), и на этих элементах определена бинарная операция, которая должна удовлетворять некоторым условиям (по сути, вести себя как сложение часов на циферблате). Число элементов в группе называется её «порядком». У порядка есть интересная особенность — если к любому элементу применить групповую операцию с ним самим Порядок раз, то получится нейтральный элемент: a^{Порядок} = Нейтраль. Этот факт следует из теоремы Лагранжа, хотя некоторые частные случаи были известны задолго до формулирования этой теоремы. Самым известным частным случаем является малая теорема Ферма.

Малая теорема Ферма интересна тем, что работает с конечной группой, построенной с использованием простого числа p. Эта группа состоит из чисел, меньших p, а групповой операцией является взятие остатка после умножения: a·b mod p. Нейтраль это 1, но вот 0 ведёт себя неправильно, необратимо уничтожая другие элементы. Поэтому мы исключаем ноль из нашей группы. Из-за этого число элементов в группе становится равно p−1. А теорема Лагранжа превращается в малую теорему Ферма: a^{Порядок} = a^p−1 = 1. Хочу подчеркнуть, что здесь мы говорим не о возведении в степень, а о применении групповой операции p−1 раз. Результат всегда будет меньше p.

Теперь представим, что мы конструируем похожую группу, но используя произвольное число N. Нам придётся исключить не только ноль, но и любое число, у которого есть делители, совпадающие с делителями N, потому что такие числа будут тоже необратимо уничтожать другие элементы. Это приводит к тому, что Порядок становится меньше N−1. Но что если всё равно a^N−1 = 1? Есть два варианта, почему это может происходить. Первый — число N простое. Второй — Порядок делит N−1: a^N−1 = a^{Порядок·d} = (a^{Порядок})^d = 1^d = 1. Такое N называют «псевдопростое число», и именно такие составные числа проходят тест Ферма. Мы можем исключить возможность второго варианта либо доказав, что подобное d просто не может существовать, либо перебрав все возможные d | N−1 и найдя для каждого такое a, что a^(N-1)/d ≠ 1. Другими словами, мы можем проверить все возможные значения Порядка, меньшие N−1, и доказать, что ни одно из них не является истинным Порядком этой группы. И этого будет достаточно, чтобы доказать, что N простое число.

Такой подход к доказательству простоты не ограничивается только рассмотренной группой, его можно обобщить и для других групп. Если вы можете построить группу, порядок которой легко вычислить для простого N, но при составном N порядок всегда отличается от этого значения, то такую группу можно использовать для доказательства простоты. Например, мы можем построить группу из последовательностей Люкá. В ней элементами будут пары (U_i mod N, V_i mod N). Групповая операция оказывается весьма нетривиальной, но на практике она реализуется довольно эффективно. Порядок этой группы на самом деле оказывается зависимым от параметров P, Q, задающих последовательности, но для простого N может принимать только два значения N−1 и N+1. Случай N−1 нам не очень интересен, поскольку повторяет предыдущую группу, которая к тому же проще в реализации. Но вот случай N+1 очень интересен, ведь он позволяет доказывать простоту чисел, у которых мы знаем все делители N+1. К тому же, для любого N мы с лёгкостью можем подобрать такие параметры P, Q, чтобы Порядок был именно N+1 (если число N простое, конечно же).

Итак, у нас получилось два вида тестов простоты. Если число имеет форму N = +1, тогда мы можем с лёгкостью разложить N−1 на простые и проверить все маленькие порядки на мультипликативной группе. Если число имеет форму N = −1, тогда мы можем с лёгкостью разложить N+1 на простые и проверить все маленькие порядки на группе последовательностей Люка. К сожалению, нам неизвестны подходящие группы для чисел, заканчивающихся на +2, −3 и вообще +c. Точнее, такие группы есть, например те же эллиптические кривые, но мы (пока?) не знаем простого метода построения эллиптической кривой для заданного +c.

Для некоторых форм тест простоты можно ещё упростить. Например, доказав, что для данной формы d не может существовать в принципе. Или доказав, что нам не нужно знать полное разложение на простые, достаточно только существенной части. В следующей таблице перечислены получившиеся тесты простоты:

Для последней строчки существует дополнительное условие, позволяющее доказывать простоту имея лишь треть разложения N±1 на простые.

С теми, кто дочитал до этого места, я бы хотел поделиться некоторыми хитростями реализации.

Наивная реализация тестов +1 сначала проверяет условие a^N−1 = 1. Но мы можем проверить случай d = 2 на первом же проходе. Для этого нам нужно выбрать a таким образом, чтобы этот элемент не был квадратом ни одного другого элемента. В этом нам поможет символ Кронекера: (a/N) = −1. После этого мы можем проверить условие a^(N−1)/2 = −1. Оно очевидно удовлетворяет и изначальному условию, но вдобавок ещё и проверяет, что у Порядка та же степень двойки, что и у N−1. Этого оказывается достаточно тестам Пепина и Прота, чтобы объявить N простым. В других тестах такое изменение может давать незначительную прибавку в скорости, а кроме того его можно использовать для контроля корректности программы (неправильное количество итераций легко не заметить, если в результате получается 1, но оно сразу проявляется при -1).

Ту же самую идею можно реализовать на стороне тестов −1. Условие простоты там формулируется как U_N+1 = 0, что эквивалентно V_N+1 = −2 и V_2(N+1) = 2 (Порядок на самом деле 2(N+1)). Но если N+1 делится на 4, и мы выбираем Q = −1, то по (Corollary 4) мы можем проверять условие V_(N+1)/2 = 0. И опять этого достаточно для тестов Люка-Лемера и Люка-Лемера-Ризеля, чтобы объявить N простым. Из описания теста Люка-Лемера может быть неочевидно, что там проверяется V_(N+1)/2 = 0, но именно это там и происходит. Тест Люка-Лемера использует последовательности Люка с параметрами P = 2^(p+1)/2, Q = −1, что удовлетворяет (Corollary 4). После первого удвоения мы получаем V₂ = 4, Q² = 1. После следующих p−2 удвоений мы получаем V_2^(p−1) = V_(N+1)/2 = 0.

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