Miller-Rabin-Selfridge Primality Test
- To: mathgroup at smc.vnet.net
- Subject: [mg39564] Miller-Rabin-Selfridge Primality Test
- From: "flip" <flip_alpha at safebunch.com>
- Date: Sun, 23 Feb 2003 05:00:58 -0500 (EST)
- Sender: owner-wri-mathgroup at wolfram.com
Hello All,
I coded the following module (and it's ugly), but it works properly and was
wondering if anyone could suggest improvements.
I wanted the ability to choose my own base (mostly to validate correctness)
and also to allow for the random choice of bases (b), so if it looks a
little strange, sorry. It mightbe useful to add a choice for multiple b's
as each iteration decreses the probabily of the number not being prime by
(1/4^iter).
Anyway, I am curious if the stat thing can be eliminated (I often have
trouble with those properly terminating). Would it be better to use a while
loop as opposed to the for loop?
Anyway, thanky you for any insights, Flip
To email me remove "_alpha". The code follows.
(* Miller - Rabin - Selfridge Primality Test for Strong Pseudoprimes base b
*)
MRS1[num_, base_] := Module[{n = num, stat = 0},
If[base == 0, b = Random[Integer, {1, n - 1}], b = base];
While[GCD[b, n] != 1, b = Random[Integer, {1, n - 1}]; b];
s = IntegerExponent[n - 1, 2]; t = (n - 1)/(2^s); w = PowerMod[b, t, n];
If[(w == 1 || w == n - 1), stat = 1];
If[stat == 0,
For[k = 1, k < s + 1 && stat == 0, w = PowerMod[b, (2^k)t, n];
If[w == n - 1, stat = 1]; k++]];
Print["MRS results for n, b, primality = ", {n, b, stat}]]
MRS1[2047, 0]
MRS1[2047, 2]