Тест простоты Рабина - Программирование от RIN.RU

Программирование

ПОИСК

Главная / Алгоритмы / Математика / Теория чисел /

8  Perl
8  PHP
8  JavaScript
8  HTML
8  DHTML
8  XML
8  CSS
8  C / C++
8  Pascal и Delphi
8  Турбо Ассемблер
8  MySQL
8  CASE-технологии
8  Алгоритмы
8  Python
8  Обратная связь
8  Гостевая книга

Тест простоты Рабина - Программирование от RIN.RU

Тест простоты Рабина

Теорема (законность теста Рабина).

Если тест Рабина выдает ответ 'm -- составное число', то m действительно является составным.
Вероятность ответа 'не знаю' для составного числа m не превосходит 1/4.

Доказательство. Докажем только первое утверждение. Если x_t =/= 1 (mod m), то m не удовлетворяет малой теореме Ферма и, следовательно, не является простым. Если же последовательность (1) содержит фрагмент ..., a, 1, ..., где a =/= +-1 (mod m), то имеем

a² == 1 (mod m), a =/= 1, a =/= -1 (mod m)
Если бы m было простым, то кольцо Z_m являлось бы полем.

Но в любом поле есть только два квадратных корня из единицы: это единица и минус единица. (По теореме Безу, число корней многочлена не превосходит его степени, квадратные корни из единицы -- это корни многочлена x² - 1.) Следовательно, число m не является простым.

Пример программы

{IsPrime.Pas ver. 2.0 (c) Max Alekseyev , 2:5015/60@FidoNet}
{Реализация вероятностного алгоритма Миллера-Рабина с 20 раундами.
Для примера выдает простые на отрезке [1000000000,1000100000].
Вероятность ошибки (то, что составное число будет названо простым) меньше
4^(-Rounds).}

const Rounds=20;

function mulmod(x,y,m:longint):longint; assembler;
asm
{$IFDEF USE32}
mov eax,x
mul y
div m
mov eax,edx
{$ELSE}
db $66; mov ax,word ptr x
db $66; mul word ptr y
db $66; div word ptr m
mov ax,dx
db $66; shr dx,16
{$ENDIF}
end;

function powmod(x,a,m:longint):longint;
var r:longint;
begin
r:=1;
while a>0 do
begin
if odd(a) then r:=mulmod(r,x,m);
a:=a shr 1;
x:=mulmod(x,x,m);
end;
powmod:=r;
end;

function isprime(p:longint):boolean;
var q,i,a:longint;
begin
if odd(p) and (p>1) then
begin
isprime:=true;
q:=p-1;
repeat q:=q shr 1; until odd(q);
for i:=1 to Rounds do
begin
{$IFDEF USE32}
a:=Random(p-2)+2; {$ELSE} a:=2+Trunc(Random*(p-2)); {$ENDIF}
if powmod(a,p-1,p)<>1 then
begin
isprime:=false; break;
end;
a:=powmod(a,q,p);
if a<>1 then
begin
while (a<>1) and (a<>p-1) do a:=mulmod(a,a,p);
if a=1 then
begin
isprime:=false; break;
end;
end;
end;
end else isprime:=(p=2);
end;

var t:longint;
begin
Randomize; {Don't forget to reset Random Generator!}
for t:=1000000000 to 1000100000 do if isprime(t) then writeln(t);end.

<<<  Назад
1  2

8  Комментарии к статье  8 8  Обсудить в чате