Фальсификация простоты

Сначала напомним классический способ проверки числа \(N\) на простоту: для каждого \(x\geqslant 2\), для которого \(x^2 \leqslant N\), проверить, делится ли \(N\) на \(x\):

• если делится, то \(N\) составное
• если не делится, то \(N\) простое

Работоспособность этого алгоритма основана на том, что если \(N=ab\) для положительных \(a\) и \(b\), то из свойств порядка действительных чисел тривиально следует, что:

• либо \(a\leqslant\sqrt{N}\)
• либо \(b\leqslant\sqrt{N}\)
• либо верно и то, и другое

Поэтому, если у \(N\) есть какой-то положительный делитель, отличный от \(1\) и \(N\), то есть и делитель (тоже отличный от \(1\) и \(N\)), не превышающий \(\sqrt{N}\).

Основная проблема этого алгоритма: долгое время работы. Например, для того, чтобы подтвердить простоту 100-значного простого числа, потребуется проверить порядка \(10^{50}\) потенциальных делителей (такую проверку невозможно осуществить при помощи известных сейчас технологий построения вычислительных устройств даже за ожидаемое время существования Солнечной системы).

Поэтому сейчас мы поговорим о более быстрых способах проверки числа на простоту.

Тест Ферма

Согласно формуле Эйлера, если \(p\) — простое и \(x\) не кратен \(p\), то

\[ x^{p-1} \equiv_p 1 \]

Напомним, что это равенство также называют Малой Теоремой Ферма.

Будем говорить, что число \(x\) удовлетворяет тесту Ферма по модулю \(N\), если

\[ x^{N-1} \equiv_N 1 \]

Оказывается, что если хотя бы одно \(x\), взаимно простое с \(N\), не удовлетворяет тесту Ферма (и тем самым доказывает, что \(N\) составное), то среди всех чисел от \(1\) до \(N-1\) тех, кто не удовлетворяет тесту Ферма, не менее половины!

Действительно, пусть \(f_1, f_2, \ldots f_n\) — все остатки по модулю \(N\), которые удовлетворяют тесту Ферма. Пусть также \(x\) не удовлетворяет тесту Ферма и взаимно прост с \(N\). Тогда, очевидно:

• все \(xf_i\) различны (поскольку \(x\) взаимно прост с \(N\))
• все \(xf_i\) не удовлетворяют тесту Ферма (поскольку \((xf_i)^{N-1}\equiv_N x^{N-1}\cdot 1\))

Поэтому остатков, не удовлетворяющих тесту Ферма, не меньше, чем удовлетворяющих.

Вероятностная верификация простоты

Отрицательный тест Ферма (для ненулевого остатка) опровергает простоту числа. Положительный тест Ферма же не доказывает простоту. Но вот многократно повторённый тест Ферма в некоторых случаях позволяет быть уверенным в простоте числа.

А именно, очевидно следующее: если существует взаимно простой с \(N\) и не удовлетворяющий тесту Ферма остаток по модулю \(N\), то вероятность сделать \(n\) положительных тестов Ферма подряд (выбирая тестируемый остаток случайным образом) не превышает \(2^{-n}\). Например, для \(n=50\) эта вероятность существенно меньше вероятности того, что в вычислениях произошла ошибка из-за космического луча, попавшего в оперативную память.

К сожалению, никакого простого способа узнать, существует ли взаимно простой с \(N\) и не удовлетворяющий тесту Ферма остаток, нет.

Более того числа, для которых таких остатков не существует, называемые числами Кармайкла, встречаются не так уж и редко (известно, например, что в пределах от \(1\) до \(x\) асимптотически хотя бы \(x^{1/3}\) чисел являются числами Кармайкла).

Поэтому требуется более сильный тест на простоту.

Тест Миллера-Рабина

Ключевой частью алгоритма Тонелли является многократное возведение в квадрат чисел вида \(a^q\), где \(q\) — нечётное число вида \((p-1)/2^s\).

При этом

• либо \(a^q\equiv_p 1\)
• либо на каком-то шаге, номер которого меньше \(s\), получится \(-1\)

Будем говорить, что \(a\) удовлетворяет тесту Миллера-Рабина по модулю \(N=2^s q + 1\), где \(q\) нечётно, если

• либо \(a^q\equiv_N 1\)
• либо менее чем \(s\)-кратное возведение \(a^q\) в квадрат даёт \(-1\) по модулю \(N\)

Оказывается, что для составного \(N\) не более четверти всех остатков удовлетворяет тесту Миллера-Рабина. Это не слишком легко доказывается, поэтому для полноты картины мы докажем более слабое (но не менее полезное) утверждение о том, что остатков, удовлетворяющих тесту Миллера-Рабина не более половины.

Недотеорема Рабина

Свойство чисел Кармайкла

Сперва заметим, что степени простых чисел не являются числами Кармайкла: если \(N=p^a\), где \(a\geqslant 2\), то \(p+1\) не удовлетворяет тесту Ферма.

Действительно, если бы \(p+1\) удовлетворяло тесту Ферма по модулю \(p^a\), то его \((N-1)\)-я степень была бы сравнима с единицей по любому модулю, делящему \(p^a\). В том числе — по модулю \(p^2\). Но

\[ (p+1)^{N-1} \equiv_{p^2} (N-1)p + 1 = p^{a+1} - p + 1 \equiv_{p^2} 1-p \]

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

Рабиновские лжецы

Если \(N\) не число Кармайкла, то мы уже доказали, что не менее половины остатков не удовлетворяют тесту Ферма (а, следовательно, и тесту Миллера-Рабина).

Осталось рассмотреть ситуацию, когда \(N\) — число Кармайкла.

Пусть \(r_1, r_2\ldots r_n\) — все остатки, удовлетворяющие тесту Миллера-Рабина. Заметим, что среди них есть число \(N-1\), которое на нулевом шаге теста даёт минус единицу. Пусть \(M\) — максимальный номер шага, на котором кто-то из \(r_i\) даёт минус единицу (в непустом конечном множестве чисел максимум всегда есть).

Рассмотрим вообще все остатки, для которых \(K\)-кратное возведение в квадрат их \(q\)-й степени даёт единицу или минус единицу. Будем называть их «хорошими». Заметим, что:

• произведение хороших остатков хорошее
• если \(h\) хороший, то он взаимно прост с \(N\)
• если \(h\) хороший, то его обратный по модулю \(N\) остаток тоже хороший
• если \(h\) хороший, а \(x\) не хороший, то \(hx\) тоже не хороший

Поскольку все \(r_i\) хорошие, то их не меньше, чем хороших остатков. А в случае, когда есть не хороший остаток, хороших остатков не более половины.

Осталось заметить, что не хороший по модулю числа Кармайкла остаток всегда есть. Пусть \(N=AB\), где \(A\) и \(B\) взаимно просты, нечётны и не менее тройки.

Пусть \(r\) — тот самый остаток, удовлетворяющий тесту, для которого требуется ровно \(K\) возведений в квадрат для получения минус единицы.

Выберем любой остаток, сравнимый с \(r\) по модулю \(A\) и сравнимый с \(1\) по модулю \(B\): такой существует благодаря КТО. \(K\)-кратный квадрат его \(q\)-й степени сравним с \(-1\) по модулю \(A\) и сравним с \(1\) по модулю \(B\).

Если бы наш остаток был хорошим, то по модулям \(A\) и \(B\) должны были получиться либо две минус единицы, либо две единицы. Но единица не сравнима с минус единицей по модулю, большему двойки!