Тест проверка квадратным корнем
В модульной арифметике, если n –простое числодиницы, то квадратный1 корень из
е modn = +1 или -1. Если n составное число, то квадратный корень можетбыть +1, -1 и другие числа.
(Напомним, что в модульной арифметике
-1=n-1(modn)
Примеры
n=7, x=1 найти mod7=? |
|||
Перебором находимх |
|||
1 |
2=1mod7 |
||
|
=4mod7 |
||
22=2mod7 |
|||
32 |
|
=1mod7 |
|
4 |
1= −3 |
|
|
62 |
= −12=4mod 7 |
||
522 |
= −222=2mod7 |
||
2 |
|
mod7=1 или -1 |
|
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 |
|
|
|
|
|
|
|
||
|
=((( |
|
|
|
= |
|
|
= |
|
|
) |
|
|
= |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|