pptest := proc (N::integer,t::integer)
#
# Probabilistischer Primzahltest, der mit
# zuf\344llig gew\344hlten Startwerten 1 < a < N
# maximal t Iterationen von
# Teilbarkeitstest,
# ggT-Test,
# Fermat-Kongruenztest
# Miller-Rabin-Test
# durchf\374hrt.
#
local a,d,e,j,k,s,u,f,found,randomelement;
randomelement := rand(2..N-1);
for s from 1 to t do
a := randomelement();
#
# Teilbarkeitstest
#
if N mod a = 0 then
RETURN(N,`ist keine Primzahl:`,a,`teilt`,N) fi;
#
# Euklid-Test
#
d := igcd(a,N);
if d>1 then
RETURN(N,`ist keine Primzahl: der GGT von`,a,`und`,N,`ist`,d) fi;
#
# Fermat-Test
#
e := a &^(N-1) mod N;
if not (e=1) then
RETURN(N,`ist keine Primzahl:
Fermat-Test mit`,a,`liefert a^(N-1) mod N =`,e) fi;
#
# Miller-Rabin-Test
#
print(`Miller-Rabin-Test wird gestartet`);
u := N-1;
k := 0;
while (u mod 2 = 0) do
u := u/2;
k := k+1;
od;
f := a &^u mod N;
print(f);
if (f=-1 mod N) or (f=1 mod N) then break fi;
found := false;
for j from 1 to k do
f := f &^2 mod N;
print(f);
if f=-1 mod N then found := true; break fi;
od;
if found then break else
RETURN(N,`ist keine Primzahl: Miller-Rabin-Test!`)
fi;
od;
print(`MR-Test`,t,`-mal bestanden:`,N,`ist vermutlich Primzahl`);
1;
end:
pptest(41,3);pptest(561,5);pptest(10007,5);isprime(10007);findprime := proc (N::integer,t::integer)
#
# die n\344chstgr\366ssere Primzahl nach N
# wird mittels probabilistische Primzahltest
# bestimmt
# t = Anzahl der Iterationen
#
local n;
n := N;
if (n mod 2 = 0) then n := n+1 fi;
while true do
if pptest(n,t)=1 then break fi;
n := n+2;
od;
end;findprime(8234857628934756343,5);isprime(%);