29 lines
514 B
Plaintext
29 lines
514 B
Plaintext
func miller_rabin(n, k=10) {
|
|
|
|
return false if (n <= 1)
|
|
return true if (n == 2)
|
|
return false if (n.is_even)
|
|
|
|
var t = n-1
|
|
var s = t.valuation(2)
|
|
var d = t>>s
|
|
|
|
k.times {
|
|
var a = irand(2, t)
|
|
var x = powmod(a, d, n)
|
|
next if (x ~~ [1, t])
|
|
|
|
(s-1).times {
|
|
x.powmod!(2, n)
|
|
return false if (x == 1)
|
|
break if (x == t)
|
|
}
|
|
|
|
return false if (x != t)
|
|
}
|
|
|
|
return true
|
|
}
|
|
|
|
say miller_rabin.grep(^1000).join(', ')
|