Инструменты сайта


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

Т

Теорема [Поклинтон]. Предположим, что доступна информация о некоторых множителях числа $ \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} \, .$$ На основании теоремы 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 $.

Теорема 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} $, поскольку1) $ \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$$ является простым.

1)
См. упражнение \ref{GCDexer1}
crypto/pprime/pockl.txt · Последние изменения: 2020/03/11 14:00 (внешнее изменение)