Тест Ферма

Многие тесты на простоту основаны на малой теореме Ферма: если $p$ простое и $a$ не делится на $p$ , то

$a^{p-1}=1~\bmod~p$

Тестом Ферма на простоту числа $n$ по основанию $a$ называется процедура:

если для основания $a$ и модуля $n$ выполняется $a^{n-1}=1~\bmod~n$ , то $n$ может быть простым числом

если $a^{n-1}\ne 1~\bmod~n$ , то $n$ - однозначно составное.

Тест Миллера

Улучшение теста Ферма основано на утверждении, что для простого $p$ , удовлетворяющего условию

$a^2=1~\bmod~p\to(a-1)(a+1)=0~\bmod~p$ ,

следует одно из двух

$a=1~\bmod~p$ ,

$a=-1~\bmod~p$ .

Любое нечетное $n$ число представимо в виде

$n=2^s r+1\to n-1=2^s r$

где $r$ - нечетное. Тогда

$a^{n-1}=(a^r)^{2^s}\bmod n$ .

Вначале вычисляем $a_0=a^{r}~\bmod~n$ и последовательно возводим в квадрат s раз:

$a_i=a^2_{i-1}~\bmod~n,~i=1,\ldots,s$ .

Для того чтобы выполнялось условие

$a_s=1~\bmod~n$ ,

необходимо выполнение одного из 2 условий

$a_0=a^r=1~\bmod~n$

$\exist i\in[0,s-1]:~a_i=-1~\bmod~n$ .

Если одно из условий выполняется, то для данного $a$ тест возвращает " $n$ возможно простое"; если не выполняется, то " $n$ однозначно составное".

Вероятностный тест Миллера - Рабина

Вероятностный тест Миллера-Рабина построен на выборе $t$ псевдослучайных чисел $a$ и проверке тестом Миллера. Если для всех $t$ чисел $a$ тест пройден, то $n$ называется псевдопростым, и вероятность того что число $n$ не простое, имеет оценку

$P_{\mathrm{error}}<\left(\frac{1}{4}\right)^{t}$

Если для какого-то числа $a$ тест не пройден, то число $n$ составное.

Сказать "Спасибо"

Проверка чисел на простоту с использованием тестов Ферма, Миллера, Миллера-Рабина (подробно).

Тест Ферма

Тест Миллера

Вероятностный тест Миллера - Рабина

Комментарии