Материал: Лекция 2 Генерирование простых чисел [восстановлен]
n=8, x=1 найти 2 1 mod8 =? 1Перебором2 находим
22=1mod8
32=4mod8
42=1mod8
52=0mod8=1mod8
−12=1mod8= 72=1mod8
корни: +1,-1, 3,5,
n=22, x=1 найти 2 1 mod22 =? 1Перебором2 находим
−1=12 mod22 =1mod22
И все другихкорней нет.
Тест Миллера-Рабина - комбинация
• |
|
|
|
|
|
2 , m − простое |
||||||||||
|
теста Ферма и квадратного корня |
|||||||||||||||
• Запишем n-1= m |
|
|
|
|
|
|
|
|
|
|
можно |
|||||
|
ТестФермаприосновании |
|
||||||||||||||
|
записать |
−1 |
)2 |
… |
|
|
( |
|
|
2 |
|
|
|
|||
|
|
|
|
|
2 |
|
|
|
|
a |
|
|||||
|
|
( |
|
|
) |
) |
2 |
|
|
|
|
|
|
|
||
|
=((( |
|
|
|
= |
|
|
= |
|
|
) |
|
|
= |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Идея алгоритма РМ
1шаг. Выбрать a такое, что НОД(a,n)=1 |
|
|||||||||
Проверить |
|
= = ±1, |
− возможнопростое, шаг1 |
|||||||
2 шаг |
Положить i=1. Найти |
|
) |
|
кшагу 2 |
|||||
|
|
|
≠ |
±1, перейти |
||||||
|
|
|
|
|
|
|
( |
|
2 |
|
|
|
|
|
= 1, − составное, поскольку кореньиз 1 |
||||||
|
) |
2 |
= |
можетбытьтолько1 или − 1, ноне Т |
||||||
( |
|
|
|
= −1, −возможнопростое, шаг1 |
||||||
|
|
|
(потомучто приследующем возведении |
|||||||
|
|
|
|
|
|
в квадрат, будет1 |
|
|||
≠ ±1, перейтикшагу 2, положив = + 1
Когда i=k-1, перейти к шагу 1 , выбрав новое a.
Итог
1. Представить n - 1 в виде 2s ∙ r , гдеr – нечетное число.
2. Сгенерировать случайное число a, такое что 2 ≤ a ≤ n −1 .
3. Вычислить y = ar mod n:
|
а) если y = ±1, то n прошло тест и возможно является простым |
|
(повторяем этот тест для другого случайно выбранного числа a); |
|
б) если y ≠ ±1 , то вычисляются y2 mod n, y4 mod n, y2j для j < s до тех |
|
пор, пока не получится -1 для некоторого j. Если такое событие |
|
происходит, повторить тест для следующего a. |
4. Если ни при каких j не выполняется шаг 3б, то число n – составное и отбрасывается как не прошедшее тест.
.
Доказывается [2, 3], что вероятность ошибки при использовании теста Миллера–Рабина аппроксимируется величиной 1/4t . Видно, что этот показатель значительно лучше, чем для теста Ферма, и все операции, необходимые для проведения этого теста, имеют полиномиальную сложность.