Изменения

Перейти к: навигация, поиск

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

2 байта добавлено, 17:22, 29 июня 2010
м
Нет описания правки
===Тест Леманна===
Если для какого-либо целого числа <tex>a</tex> меньшего <tex>n</tex> не выполняется условие <tex>a^\frac{n-1}{2}=\pm 1\pmod n</tex>, то число <tex>n<tex> {{---}} составное. Если это условие выполняется, то число <tex>n</tex> {{---}} возможно простое, причем вероятность ошибки не превышает <tex>50\%</tex>.
Этот тест можно естественным образом улучшить, если извлекать корень по модулю не один раз, а столько, сколько получится.
20
правок

Навигация