30 lines
418 B
Text
30 lines
418 B
Text
import util.rnd
|
|
|
|
def isProbablyPrimeMillerRabin( n, k ) =
|
|
d = n - 1
|
|
s = 0
|
|
|
|
while 2|d
|
|
s++
|
|
d /= 2
|
|
|
|
repeat k
|
|
a = rnd( 2, n )
|
|
x = a^d mod n
|
|
|
|
if x == 1 or x == n - 1 then continue
|
|
|
|
repeat s - 1
|
|
x = x^2 mod n
|
|
|
|
if x == 1 then return false
|
|
|
|
if x == n - 1 then break
|
|
else
|
|
return false
|
|
|
|
true
|
|
|
|
for i <- 3..100
|
|
if isProbablyPrimeMillerRabin( i, 5 )
|
|
println( i )
|