Anonymous user
Miller–Rabin primality test: Difference between revisions
Adding a Standard ML version, based on my Scheme solution to SICP ex. 1.28.
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:
(n millerRabinTest: 10) ifTrue: [ n printNl ]
].</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}}==
| |||