Miller–Rabin primality test: Difference between revisions
Content added Content deleted
m (add a comment that junctive-ors are to expensive today) |
(Adding a Standard ML version, based on my Scheme solution to SICP ex. 1.28.) |
||
Line 1,466: | Line 1,466: | ||
(n millerRabinTest: 10) ifTrue: [ n printNl ] |
(n millerRabinTest: 10) ifTrue: [ n printNl ] |
||
].</lang> |
].</lang> |
||
=={{header|Standard ML}}== |
|||
<lang sml> |
|||
fun expmod base 0 m = 1 |
|||
| expmod base exp m = |
|||
if exp mod 2 = 0 |
|||
then let val rt = expmod base (exp div 2) m; |
|||
val sq = (rt*rt) mod m |
|||
in if sq = 1 |
|||
andalso rt <> 1 (* ignore the two *) |
|||
andalso rt <> (m-1) (* 'trivial' roots *) |
|||
then 0 |
|||
else sq |
|||
end |
|||
else (base*(expmod base (exp-1) m)) mod m; |
|||
local val rng = Random.rand (~643785970, ~401175694) (* arbitrary pair to seed RNG *) |
|||
in fun trial n 0 = true |
|||
| trial n t = let val a = Random.randRange (1,n-1) rng |
|||
in (expmod a (n-1) n) = 1 |
|||
andalso trial n (t-1) |
|||
end |
|||
end; |
|||
fun miller_rabin n = trial n 20; |
|||
fun trylist label lst = (label, ListPair.zip (lst, map miller_rabin lst)); |
|||
trylist "test the first six Carmichael numbers" [561, 1105, 1729, 2465, 2821, 6601]; |
|||
trylist "test some known primes" [7369, 7393, 7411, 27367, 27397, 27407]; |
|||
(*** sample run: |
|||
Standard ML of New Jersey v110.72 [built: Sun Nov 6 21:16:05 2011] |
|||
[opening 1-28.sml] |
|||
val expmod = fn : int -> int -> int -> int |
|||
[autoloading] |
|||
[library $SMLNJ-LIB/Util/smlnj-lib.cm is stable] |
|||
[autoloading done] |
|||
val trial = fn : int -> int -> bool |
|||
val miller_rabin = fn : int -> bool |
|||
[autoloading] |
|||
[autoloading done] |
|||
val trylist = fn : 'a -> int list -> 'a * (int * bool) list |
|||
val it = |
|||
("test the first six Carmichael numbers", |
|||
[(561,false),(1105,false),(1729,false),(2465,false),(2821,false), |
|||
(6601,false)]) : string * (int * bool) list |
|||
val it = |
|||
("test some known primes", |
|||
[(7369,true),(7393,true),(7411,true),(27367,true),(27397,true), |
|||
(27407,true)]) : string * (int * bool) list |
|||
***) |
|||
</lang> |
|||
=={{header|Tcl}}== |
=={{header|Tcl}}== |