Теорема Поклингтона.


Пусть n=RF+1, F= - каноническое разложение.

Если a: 1) an—1≡1(mod n);

2) 1(mod n) .

p≡1(mod F) для любого простого p\n.

Итак, если разложить n—1 на два сомножителя n—1=RF, где F> —1, то, если для некоторого a будут выполнены условия Теоремы Поклингтона (1) и (2), то n – простое.

Таким образом, можно значительно сократить количество проверок по сравнению с тестом Миллера.

Замечание.

Если n=RF+1 – нечетное простое число, F> —1, F= , НОД(R,F)=1, то вероятность того, что случайно выбранное 1<a<n будет удовлетворять условиям (1), (2) теоремы Поклингтона, есть .

Замечание.

Если известно полное разложение n—1, то в качестве F следует брать число, составленное из наибольших делителей n—1 для того, чтобы:

1) сократить число проверок условия (2) для каждого a;

2) уменьшить степени, в которые возводится a на этапе проверки (2);

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

 

Пример.

n=4021. —1<63.

n—1=4020=22·3·5·67. F=67, R=22·3·5=60.

Проверка условий:

a=2.

1) 24020 mod 4021=1.

2)260—1 mod 4021=1451.

НОД(4021,1451)=1.

n=4021 – простое число.

(Заметим, что вероятность того, что наугад выбранное a будет удовлетворять условиям теоремы Поклингтона для данного примера, есть (1—1/67)≈0,985).

 



Дата добавления: 2018-11-26; просмотров: 784;


Поиск по сайту:

Воспользовавшись поиском можно найти нужную информацию на сайте.

Поделитесь с друзьями:

Считаете данную информацию полезной, тогда расскажите друзьям в соц. сетях.
Poznayka.org - Познайка.Орг - 2016-2024 год. Материал предоставляется для ознакомительных и учебных целей.
Генерация страницы за: 0.009 сек.