Изменения

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

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

1 байт добавлено, 06:40, 14 мая 2011
Тест Леманна
===Тест Леманна===
Если для какого-либо целого числа <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>.
Этот тест можно естественным образом улучшить, если извлекать корень по модулю не один раз, а столько, сколько получится.
Анонимный участник

Навигация