Тест простоты Рабина
Страница 4. Реализация вероятностного алгоритма Миллера-Рабина

Реализация вероятностного алгоритма Миллера-Рабина

{IsPrime.Pas ver. 2.0 (c) Max Alekseyev <
 Этот e-mail защищен от спам-ботов. Для его просмотра в вашем браузере должна быть включена поддержка Java-script
 >, 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.

На данном контрпримере можно легко проследить, что число 341 не теореме, только в том случае,если основание простое, если же составное, то данное число удовлетворяет теореме.Руководствуясь этим утверждением можно доказать, что данная теорема действительна при , если основание составное. Таким образом можно сказазать,что и простые числа подчиняются разным законам.Или это не так? Вообще интересен ход мыслей Ферма, каким образом он вывел эту теорему.