       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]

```

• Prev by Date: Re: Finding the closest number from a list
• Next by Date: Re: Programing in MATHEMATICA
• Previous by thread: Re: Cursors in graphics
• Next by thread: how do i insert a diagram in mathematica?