34 lines
640 B
Plaintext
34 lines
640 B
Plaintext
procedure main(A)
|
|
every n := !A do write(n," is ",(mrp(n,5),"probably prime")|"composite")
|
|
end
|
|
|
|
procedure mrp(n, k)
|
|
if n = 2 then return ""
|
|
if n%2 = 0 then fail
|
|
nm1 := decompose(n-1)
|
|
s := nm1[1]
|
|
d := nm1[2]
|
|
every !k do {
|
|
a := ?(n-2)+1
|
|
x := (a^d)%n
|
|
if x = (1|(n-1)) then next
|
|
every !(s-1) do {
|
|
x := (x*x)%n
|
|
if x = 1 then fail
|
|
if x = (n-1) then break next
|
|
}
|
|
fail
|
|
}
|
|
return ""
|
|
end
|
|
|
|
procedure decompose(nm1)
|
|
s := 1
|
|
d := nm1
|
|
while d%2 = 0 do {
|
|
d /:= 2
|
|
s +:= 1
|
|
}
|
|
return [s,d]
|
|
end
|