Services & Resources / Wolfram Forums
-----
 /
MathGroup Archive
2003
*January
*February
*March
*April
*May
*June
*July
*August
*September
*October
*November
*December
*Archive Index
*Ask about this page
*Print this page
*Give us feedback
*Sign up for the Wolfram Insider

MathGroup Archive 2003

[Date Index] [Thread Index] [Author Index]

Search the Archive

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?