существует весьма эффективный критерий
Простые числа вида k*2n +1
Для чисел вида k*2n+ 1 существует весьма эффективный критерий простоты. Он состоит в проверке сравнения а2n-1 =-1 (mod k*2n +1) для некоторого а. Однако выбор этого а зависит от k. Оказывается, нужно различать случаи, когда k не делится на 3 и делится на 3. Случай, когда k не делится на 3, совсем прост.
Случай, когда k не делится на 3
Если k не делится на 3, то, как заметил Прот (Proth) в 1878 году, числа k*2n +1 являются простыми при kn + 1 тогда и только тогда, когда 32n-1-1 (mod k-2n+l). Впрочем, эта традиционная формулировка критерия Прота несколько некорректна. В ней, например, (молчаливо!) исключается случай n = 1, k = 1. Для n =1, k - 1 имеем k = k3 = 2+1= 2" + 1, хотя З2""* =3sO (mod /n2n+1), причем *-2"+1 =3-простое число. Дело в том, что если число k-2n +1 простое, то в традиционной формулировке критерия Прота число3 должно быть квадратичным невычетом по модулю k-2n + l. Но при и= 1, k= 1 число k2n+l =3. Впрочем, n- 1, k- 1 — единственное решение уравнения k* 2n +1 =3 в целых числах, отличных от 0. (Уравнение k-2" + 1 =3 в целых числах имеет всего два решения: указанное только что решение n= 1, k= 1 и n = 0, k= 2.)
Разыскивая простые числа вида k*2n +1, конечно, нельзя ограничить перебор по и только простыми числами, но все равно многие значения отсеиваются тривиальным образом.
Пример 7.7. Простые числа вида 5-2n + 1. Рассмотрим, например, случай k = 5. Тогда числа вида 5*2n +1 делятся на 3 при четных п. Так что перебор можем вести только по нечетным и.
Используя функцию PowerMod, очень легко запрограммировать критерий простоты.
MknPrime[k_,n_]:=Module[{t = k*2An+l},
If[k<=2An+l,PowerMod[3,(t-1)/2,t]==t-l,PrimeQ[t]]]
А вот и программа для перебора по нечетным п.
Mkn[k_,nl_]:=Block[{n=l},
While [n<=nl, {If[MknPrime[k,n],Print[п]], n+=2}]];
Теперь можем выполнить перебор. Mkn[5,300000]
Так можно получить (если хватит терпения) следующие значения я: 1, 3, 7, 13, 15, 25, 39, 55, 75, 85, 127, 1947, 3313, 4687, 5947, 13165, 23473, 26607, 125413, 209787, 240937.
Впрочем, при дневном счете терпение обычно улетучивается после печати числа 13165, если не раньше. Конечно, метод перебора можно усовершенствовать, заметив, что если остаток от деления и на 3 равен 2, то число 5*2n +1 делится на 7. Так что числа, дающие в остатке 2 при делении на 3, можно при переборе пропустить. Можно также пропустить числа, дающие в остатке 1 при делении на 10, поскольку тогда число 5*2n + 1 делится на 11. Можно, конечно, пойти и дальше. Можно, например, взять несколько небольших нечетных простых чисел д, для которых существует решение сравнения 5-2n + 130 (mod q). Пусть s— показатели 2 по модулю q: 2s=1 (mod q). (Такое 5 можно найти с помощью функции MultiplicativeOrder [2, q].) Тогда при всех n^t (mod s) 5*2n + 1 = 0 (mod q). Если q не является числом вида 5*2n +1, все числа nst (mod s) можно опустить при переборе. Если же q является числом вида 5*2n +1, то нужно оставить только то число rmt (mod s), при котором 5*n + 1 = q. Эта идея вполне реализуема, но не слишком ли она усложняет перебор?
Давайте попробуем. Вот функция, которая по заданному номеру я простого числа q находит t — решение сравнения 5* 2n +1 = О (mod q) и i — показатель 2 по модулю q, если такое решение существует.
:[n]:= 51ock[{q= Prime[n], s=MultiplicativeOrder[2,q], t=MultiplicativeOrder[2,q,{-PowerMod[5,-I, q]} ] }, If[NumberQft],fs,t}]]
Теперь с помощью этой функции можно сгенерировать таблицу остатков и соответствующих им модулей.
