20190321, 10:32  #1  
"Rashid Naimi"
Oct 2015
Out of my Body
2·3^{2}·101 Posts 
Lucas Primality Test
Hi folks,
https://en.m.wikipedia.org/wiki/Lucas_primality_test Quote:
1 < a < n1  For n=7 & a=6 7  6^61 & 7  6^21 Wouldn't the test fail (be always inconclusive) for all primes n and base a=n1 ? Thank you for any clarification in advance. Last fiddled with by a1call on 20190321 at 10:57 

20190321, 11:08  #2  
Jun 2003
11·421 Posts 
Quote:
1^((n1)/q) will be 1 if (n1)/q is even, which is pretty much true for all odd n > 3 and q>2. In fact, extending the argument a bit, I think you can restrict to 1 < a <= (n1)/2 (maybe  I haven't tried to work out if a & a behaves identically under this test for all conditions). 

20190321, 15:51  #3 
"Rashid Naimi"
Oct 2015
Out of my Body
2×3^{2}×101 Posts 
Yes, there is a symmetry there which was also the basis of my 1/2 price Fermat test thread.
I am glad there is at least one vocal member here that can wrap his head around the subject. a=1 and a=n1 are in a way equivalent. There is probably room for improvement in formulating the base of a primality test than just giving it as a range. Thank you for your reply axn. Last fiddled with by a1call on 20190321 at 15:55 
20190321, 16:12  #4 
"Dana Jacobsen"
Feb 2011
Bangkok, TH
2·11·41 Posts 
Page 173174 of Crandall and Pomerance discusses this particular test. The theorem itself has no restrictions on a. Their remark is that one chooses random 1 <= a <= n1. I'm not sure why one would choose a=1. In my certificates I require 1 < a < n.
Usually you don't need to look very far to find a suitable a, albeit this assumes we're already done a reasonable compositeness test so we're generally not running this on composites. It also helps to use one of the extensions such as those in BLS75. Theorem 1, for example, lets us use different a values for each factor. Theorem 3 means we don't need all the factors. Theorem 5 is quite broad and lets us factor even less [N/2)^(1/3) for the simpler version with m=1]. All of that is really to say that the theorem doesn't require such restrictions, and in practice we find a suitable a very rapidly if n is prime. So what is the point? We wouldn't want to use this on composites, looping until n/2 anyway. Last fiddled with by danaj on 20190321 at 16:14 
20190321, 16:26  #5 
"Rashid Naimi"
Oct 2015
Out of my Body
11100011010_{2} Posts 
Well mathematics is the most exact of the sciences. If a range statements is given it is a traditional practice to clip out bounds which will yield inconclusive results. Redundant ranges are more excusable perhaps.
Last fiddled with by a1call on 20190321 at 16:28 
20190321, 16:36  #6 
"Dana Jacobsen"
Feb 2011
Bangkok, TH
2·11·41 Posts 
Good point. The sources don't even include a range for a in the theorems so they sidestep it that way. Only when one has to actually go implement something to *find* a suitable value does this come up.

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Lucas Primality Test in Pari GP  a1call  PARI/GP  11  20180826 09:39 
Modifying the Lucas Lehmer Primality Test into a fast test of nothing  Trilo  Miscellaneous Math  25  20180311 23:20 
The Lucas Primality Test  Mr. P1  Math  6  20090531 20:03 
A primality test for Fermat numbers faster than Pépin's test ?  T.Rex  Math  0  20041026 21:37 
LucasLehmer primality test  CMOSMIKE  Math  5  20020906 18:46 