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


Вход: n=2sr+1 – нечетное число, проверяемое на простоту, s≥0, r – нечетное.

t - количество итераций, параметр надежности.

1. Повторить t раз следующие шаги:

1.1. Случайным образом выбрать a: 1<a<n—1.

1.2. Строим последовательность b0, b1,…,bs, где bj= mod n, j=0,1,…,s.

1.3. Если в построенной последовательности не встретилась «1», то идти на Выход с сообщением «n - составное число».

1.4. Если перед первой единицей в последовательности стоит не «-1», то идти на Выход с сообщением «n - составное число».

2. Идти на Выход с сообщением «n – простое число с вероятностью εt».

Выход.

Обратим внимание на то, что в последовательности b0, b1,…,bs каждый последующий член является квадратом предыдущего по модулю n, а последний член есть ни что иное как an—1 mod n.

Вероятность ошибки ε ≤ φ(n)/4n, то есть верхняя граница ошибки на одной итерации для теста Миллера-Рабина в 2 раза меньше аналогичной для теста Соловея-Штрассена и в 4 раза – для теста Ферма.

Пример 1.

n=65=64+1=26+1. r=1, s=6.

t=5.

1. 1-я итерация:

1.1. a=8.

1.2. Составляем последовательность: 8, 64=—1, 1, 1, 1, 1.

1.3. В последовательности встретилась «1».

1.4. Перед первой единицей стоит —1.

1. 2-я итерация:

1.1. a=11.

1.2. Составляем последовательность: 11, 56, 16, 61, 16, 61.

1.3. В последовательности не встретилась «1».

Выход: « n - составное число».

 

В том случае, когда тест Миллера-Рабина определяет составность числа n на шаге 1.4, появляется возможность частично факторизовать n.

Действительно, пусть в последовательности b0, b1,…,bs, где bj= mod n, нашлось такое i, что bi≠±1, bi+1=1. Обозначим для краткости bi=b. Тогда bi+1=b2≡1(mod n). Тогда n\(b2—1) n\(b+1)(b—1). Но в силу того, что b ±1(mod n), n не делит (b+1), n не делит (b—1). Следовательно,

1<НОД(n, b—1)<n,1<НОД(n, b+1)<n.

Значит, НОД(n,b—1) и НОД(n,b+1) являются нетривиальными делителями числа n.

Пример 2

n=161=160+1=25·5+1. r=5, s=5.

1. 1-я итерация:

1.1. a=22. a5 mod 161 = 225 mod 161=22.

1.2. Составляем последовательность: 22, 1, 1, 1, 1, 1.

1.3. В последовательности встретилась «1».

1.4. Перед первой единицей стоит 22.

Выход: « n - составное число».

Факторизуем 161: b=22. b+1=23, b—1=21.

Вычислим НОД(161, 23): 161=23·7+0.

НОД(161,21): 161=21·7+14

21=14·1+7

14=7·2+0.

Итак, нашли два нетривиальных делителя 161, и получили 161=23·7.

Надо заметить, что на самом деле случай, когда в тесте Миллера-Рабина возникает возможность факторизации, происходит весьма редко. Гораздо чаще сообщение о составности мы получаем на шаге 1.3.

 



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


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

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

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

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