Тест Рабина-Миллера

Пусть n - нечетное и , t - нечетное. Если число n является простым, то при всех выполняется сравнение . Поэтому, рассматривая элементы можно заметить, что люби среди них найдётся равный , либо .

На этом замечании основан следующий вероятностный тест простоты:

1) Выбираем случайное число "a" из интервала {1,.....,n-1} и проверяем с помощью алгоритма Евклида условие (a,n)=1;

2) Если оно не выполняется, то ответ "n - составное".

3) Вычисляем ,

4) Если получили значение , то ответ неизвестен

5) Вычисляем , до тех пор, пока не появится -1;

6) Если ни одно из этих чисел не равно -1, то ответ "n - составное";

7) Если мы достигли -1, то ответ неизвестен.

Арифметическая сложность данного теста, очевидно, составляет O(sn).

Пример:

Пусть n=97;

n-1=96=32*3=2⁵*3; т.е 2^s=2⁵, а t=3;

1) Выбираем случайное число ;

Пусть a = 5, проверяем его: (5,97)=1;

3) Вычисляем ;

;

;

=> => Вывод: Ответ неизвестен, вероятно число простое.

Дата добавления: 2015-09-06