Иллюстрированный самоучитель по Mathematica 5

Простые числа вида k * 2 n +1

Для чисел вида k*2ⁿ +1 существует весьма эффективный критерий простоты. Он состоит в проверке сравнения а2^n-1 =-1 (mod k*2ⁿ +1) для некоторого а. Однако выбор этого а зависит от k. Оказывается, нужно различать случаи, когда k не делится на 3 и делится на 3. Случай, когда k не делится на 3, совсем прост.

Случай, когда k не делится на 3

Если k не делится на 3, то, как заметил Прот (Proth) в 1878 году, числа k*2ⁿ +1 являются простыми при kⁿ + 1 тогда и только тогда, когда 3^{2 n-1} -1 (mod k-2ⁿ +l). Впрочем, эта традиционная формулировка критерия Прота несколько некорректна. В ней, например, (молчаливо!) исключается случай n = 1, k = 1. Для n =1, k -1 имеем k = k3 = 2+1= 2" + 1, хотя З2""* =3s0 (mod / n 2ⁿ +1), причем *-2"+1 =3-простое число. Дело в том, что если число k-2ⁿ +1 простое, то в традиционной формулировке критерия Прота число 3 должно быть квадратичным невычетом по модулю k-2ⁿ + l. Но при и= 1, k= 1 число k2ⁿ +l =3. Впрочем, n -1, k -1 – единственное решение уравнения k* 2ⁿ +1 =3 в целых числах, отличных от 0. (Уравнение k-2" + 1 =3 в целых числах имеет всего два решения: указанное только что решение n = 1, k= 1 и n = 0, k= 2.)

Разыскивая простые числа вида k*2ⁿ +1, конечно, нельзя ограничить перебор по и только простыми числами, но все равно многие значения отсеиваются тривиальным образом.

Пример 7.7. Простые числа вида 5-2ⁿ + 1.

Рассмотрим, например, случай k = 5. Тогда числа вида 5*2ⁿ +1 делятся на 3 при четных n. Так что перебор можем вести только по нечетным n.

Используя функцию PowerMod, очень легко запрограммировать критерий простоты.

А вот и программа для перебора по нечетным n.

Теперь можем выполнить перебор.

Так можно получить (если хватит терпения) следующие значения n:

Впрочем, при дневном счете терпение обычно улетучивается после печати числа 13165, если не раньше. Конечно, метод перебора можно усовершенствовать, заметив, что если остаток от деления и на 3 равен 2, то число 5*2ⁿ +1 делится на 7. Так что числа, дающие в остатке 2 при делении на 3, можно при переборе пропустить. Можно также пропустить числа, дающие в остатке 1 при делении на 10, поскольку тогда число 5*2ⁿ + 1 делится на 11. Можно, конечно, пойти и дальше. Можно, например, взять несколько небольших нечетных простых чисел д, для которых существует решение сравнения 5-2ⁿ + 130 (mod q). Пусть s– показатели 2 по модулю q: 2s= 1 (mod q). (Такое 5 можно найти с помощью функции MultiplicativeOrder [2, q].) Тогда при всех n^t (mod s) 5*2ⁿ + 1 = 0 (mod q). Если q не является числом вида 5*2ⁿ +1, все числа nst (mod s) можно опустить при переборе. Если же q является числом вида 5*2ⁿ +1, то нужно оставить только то число rmt (mod s), при котором 5*ⁿ + 1 = q. Эта идея вполне реализуема, но не слишком ли она усложняет перебор?

Давайте попробуем. Вот функция, которая по заданному номеру я простого числа q находит t – решение сравнения 5* 2ⁿ +1 = О (mod q) и i – показатель 2 по модулю q, если такое решение существует.