Система Orphus

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

Тест Ферма

Многие тесты на простоту основаны на малой теореме Ферма: если 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 составное.


Система Orphus

Комментарии