31 lines
418 B
Text
31 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 )
|