Тем не менее (даже имея в виду такую возможность дополнительного контроля)
хотелось бы иметь некоторый алгоритм построения достаточно больших простых чисел, дающий абсолютную
гарантию их простоты. Один из таких алгоритмов основан на следующем результате.
!!Т!! **Теорема [Поклинтон].** //Предположим, что доступна
информация о некоторых множителях числа// $ \widetilde{p}-1 $:
$$\widetilde{p}-1=Q\cdot M_1 \, ,$$
//где каноническое разложение//
$$
M_1=p_1^{{\mathfrak m}_1}\times \dots \times p_K^{{\mathfrak m}_K}
$$
//считается известным. Если существует// $ A $ //такое, что//
$$
A^{\widetilde{p}-1} \equiv 1 \pmod{\widetilde{p}} \quad u \quad
\operatorname{HOD}\left(A^{(\widetilde{p}-1)/p_j}-1,\widetilde{p} \right)=1
\ npu \ j\in\{1,\dots,K \} \ ,
$$
//то для любого простого множителя// $ p $ //числа// $ \widetilde{p} $ //справедливо//:
$$
p\equiv 1 \pmod{M_1} \, .
$$
//В частности, если// $ M_1>\sqrt{\widetilde{p}}-1 $, //то число// $ \widetilde{p} $ --- //простое.//
**Доказательство.** Первое из условий гарантирует, что число
$ A^{\widetilde{p}-1}-1 $ делится на $ \widetilde{p} $, а следовательно, и на
любой простой множитель этого числа:
$$A^{\widetilde{p}-1} \equiv 1 \pmod{p} \, .$$
На основании ((modular:index#первообразный_корень теоремы 3)), порядок $ \operatorname{ord} A $ по модулю $ p $ должен быть
делителем числа $ \widetilde{p}-1 $.
Второе из условий теоремы гарантирует, что
$$A^{(\widetilde{p}-1)/p_j}-1 \equiv 1 \not\equiv 0 \pmod{p} $$
для любого простого множителя $ p_j $ числа $ M_1 $. Сдедовательно, $ \operatorname{ord} A $
не может быть делителем числа $ (\widetilde{p}-1)/p_j $.
Утверждается, что $ \operatorname{ord} A $ должен делиться на $ p_j^{{\mathfrak m}_j} $.
В самом деле, мы получили, что $ \operatorname{ord} A $ принадлежит множеству делителей
числа
$$p_1^{{\mathfrak m}_1}\times \dots \times p_j^{{\mathfrak m}_j} \times \dots \times
p_K^{{\mathfrak m}_K}Q \, ,$$
но не принадлежит множеству делителей числа
$$p_1^{{\mathfrak m}_1}\times \dots \times p_j^{{\mathfrak m}_j-1} \times \dots \times
p_K^{{\mathfrak m}_K}Q \, .$$
Следовательно, он должен принадлежать разности этих множеств. На основании
теоремы \ref{GCDt26} получаем, что эта разность состоит из чисел вида
$ p_j^{{\mathfrak m}_j} q $ при $ q\in \mathbb N $. Таким образом, действительно,
$ \operatorname{ord} A $ должен иметь делителем $ p_j^{{\mathfrak m}_j} $, а поскольку
все простые числа $ p_1,\dots, p_K $ различны, то по теореме \ref{GCDt231}, $ \operatorname{ord} A $
делится на $ M_1 $.
((modular:index#первообразный_корень Теорема 3)) утверждает, что $ p-1 $ делится на порядок любого
числа $ A $ по модулю $ p $. Отсюда получаем
$$p-1 \equiv 0 \pmod{M_1} \, .$$
Пусть теперь последнее сравнение имеет место при
$ M_1>\sqrt{\widetilde{p}}-1 $.
Если бы число $ \widetilde{p} $ было составным, то любой его простой множитель
$ p $ не превосходил бы $ \sqrt{\widetilde{p}} $, но тогда число $ p-1 $ не
могло бы делиться на $ M_1 $.
♦
Итак, теорема позволяет дать заключение о простоте числа $ \widetilde{p} $ на
основании //частичной// информации о множителях числа $ \widetilde{p}-1 $.
Рассмотрим простейший случай, когда $ \widetilde{p}-1=Qp_1 $ при простом $ p_1 $.
Будем выбирать произвольное четное число $ Q\in \{2,\dots,p_1+1\} $ и для
каждого числа $ Qp_1+1 $ проверять выполнимость условий (\ref{Pocle1}) при
последовательном выборе чисел $ A $.
!!Т!! **Теорема.** Если число $ \widetilde{p}=Qp_1+1>2 $ ---
простое, то имеется ровно $ \widetilde{p}-Q-1 $ чисел $ A $ из множества
$ \{1,\dots, \widetilde{p} -1 \} $, для которых будут выполняться условия
теоремы Поклинтона.
Иными словами, при простом числе $ \widetilde{p} $, вероятность того, что
наугад выбранное из множества $ \{1,\dots, \widetilde{p} -1 \} $ число $ A $ будет
удовлетворять условиям (\ref{Pocle1}) равна $ 1-1/p_1 $, т.е. будет достаточно
высокой для больших $ p_1 $. Следовательно, если какое-то из этих условий не
удовлетворяется для выбранного $ A $, то не имеет большого смысла искать
другое, им удовлетворяющее. Разумнее будет
перейти к другому числу $ Q $, т.е. протестировать другого кандидата
$ \widetilde{p} $ на простоту.
Для проверки второго из условий (\ref{Pocle1}) достаточно
проводить вычисления $ A^{(\widetilde{p}-1)/p_j} $
по модулю $ \widetilde{p} $, поскольку[[См. упражнение \ref{GCDexer1}]]
$ \operatorname{HOD}(B,M) $ совпадает с $ \operatorname{HOD}( B \pmod{M},\, M) $.
!!П!! **Пример.** Построить $ 16 $-тизначное простое число.
**Решение.** Начнем с числа $ p_1=97 $, простота которого нам известна.
Проверим на простоту число
$$\widetilde{p}=p_1(p_1+1)+1 = 9507 ,$$
максимально возможное в теореме Поклинтона. Первое из условий
теоремы не удовлетворяется уже при $ A=2 $: $ 2^{9506} \equiv 4\pmod{9507} $.
Берем число поменьше:
$$\widetilde{p}=p_1(p_1-1)+1 = 9313 \, .$$
Поскольку $ 2^{9312} \equiv 7836 \not\equiv 1 \pmod{9313} $, то и его отбрасываем.
Далее, числа
$$p_1(p_1-3)+1 =9119 \ , \ p_1(p_1-5)+1= 8925 $$
очевидно не являются простыми. Очередное число
$$\widetilde{p}= p_1(p_1-7)+1 =8731 $$
удовлетворяет обоим условиям теоремы при $ A=2 $:
$$2^{8730} \equiv 1 \pmod{8731} \ u \ 2^{90}\equiv 5222 \pmod{8731}
\ \Rightarrow \ \operatorname{HOD} \left(2^{90}-1,8731 \right)=1 \, .$$
Следовательно, оно является простым. Обозначим его за $ p_1 $ и повторим
процедуру: число
$$\widetilde{p}=p_1(p_1+1)+1 = 76239093$$
не удовлетворяет условиям теоремы при $A=2$. А вот следующее за ним
(по убыванию) число
$$\widetilde{p}=p_1(p_1-1)+1 = 76221631 $$
удовлетворяет этим условиям при $ A=2 $, и, следовательно, является простым.
Оно уже имеет $ 8 $ цифр в десятичном представлении. Можно ожидать, что
следующий цикл приведет к решению нашей задачи.
Снова переобозначиваем: $ p_1 := 76221631 $. Здесь успех нас ожидает на
третьем шаге: число
$$\widetilde{p}=p_1(p_1-3)+1 = 5809736803635269$$
является простым.