Lucas Sequences and Primaility Testing ... Please Help
- To: mathgroup at smc.vnet.net
- Subject: [mg29281] Lucas Sequences and Primaility Testing ... Please Help
- From: Flip at safebunch.com
- Date: Mon, 11 Jun 2001 04:38:24 -0400 (EDT)
- Sender: owner-wri-mathgroup at wolfram.com
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
Mathematica.
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
looping.
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).
Algorithm:
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
steps.
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