MathGroup Archive 2001

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

Search the Archive

Lucas Sequences and Primaility Testing ... Please Help

  • To: mathgroup at
  • Subject: [mg29281] Lucas Sequences and Primaility Testing ... Please Help
  • From: Flip at
  • Date: Mon, 11 Jun 2001 04:38:24 -0400 (EDT)
  • Sender: owner-wri-mathgroup at

Hi All,

Mathematica uses the Miller-Rabin-Selfridge and the Lucas Primality tests in PrimeQ.

I have (which looks simple on paper) the algorithm for the Lucas Sequence based
primality test listed below, but I am not sure how difficult it is to code up in

I was wondering if someone here could help with coding this up?  The trickiest
part seems to be the conversion to binary to know how many times to perform the

Here is the algorithm ... any help would be appreciated (sometimes I wish Mathematica
would allow access to these routines individually so I wouldn't have to spend so
much time figuring them out ... and this algorithm was quite difficult to
find!).  Thank you for any assistance (I'll try to code it up too and see how
far I can get).


Inputs: N, an odd integer. Outputs: N prime? (Yes/No)
Find the first D in the sequence {5,-7,9,-11,13,-15,17,...} for which the Jacobi
symbol (D/N) = -1 (Mathematica has a JacobiSymbol routine).
Set P = 1 and Q = (1-D)/4.
If U(subscript N+1) = 0 mod N, then N is probably prime.
To calculate Uk where K = N+1, from the Lucas sequence, perform the following
Step 1: Let D = (P^2 ? 4Q) = (1 ? 4Q).
Step 2: Let Kr, Kr-1 ... K0 (all subscripted) be the binary expansion of K.
Step 3: Set U = 1 and V = P.
Step 4: For i = r-1 to 0,
Set (U, V) = (UV mod N, (V^2 + DU^2)/2 mod N)
If Ki = 1, then also set
(U, V) = ( (PU +V)/2 mod N, (PV + DU)/2 mod N)
Step 5: Uk = U and Vk = V

  • Prev by Date: Re: Regress, Eliminate Outliers, Regress
  • Next by Date: 3D Statistics?
  • Previous by thread: Re: Restting Probabilities
  • Next by thread: 3D Statistics?