mersenneforum.org Lucas Primality Test
 Register FAQ Search Today's Posts Mark Forums Read

2019-03-21, 10:32   #1
a1call

"Rashid Naimi"
Oct 2015
Remote to Here/There

1000100000002 Posts
Lucas Primality Test

Hi folks,

https://en.m.wikipedia.org/wiki/Lucas_primality_test

Quote:
 Let n be a positive integer. If there exists an integer a, 1 < a < n, such that
Shouldn't that be
1 < a < n-1

----------
For n=7 & a=6

7 | 6^6-1
&
7 | 6^2-1

Wouldn't the test fail (be always inconclusive) for all primes n and base a=n-1 ?

Thank you for any clarification in advance.

Last fiddled with by a1call on 2019-03-21 at 10:57

2019-03-21, 11:08   #2
axn

Jun 2003

22·1,301 Posts

Quote:
 Originally Posted by a1call For n=7 & a=6 7 | 6^6-1 & 7 | 6^2-1 Wouldn't the test fail (be always inconclusive) for all prime n and a=n-1 ?
n-1 can be written as -1 (when doing things modulo).

-1^((n-1)/q) will be 1 if (n-1)/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 <= (n-1)/2 (maybe - I haven't tried to work out if a & -a behaves identically under this test for all conditions).

 2019-03-21, 15:51 #3 a1call     "Rashid Naimi" Oct 2015 Remote to Here/There 1000100000002 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=n-1 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 2019-03-21 at 15:55
 2019-03-21, 16:12 #4 danaj   "Dana Jacobsen" Feb 2011 Bangkok, TH 32×101 Posts Page 173-174 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 <= n-1. 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 2019-03-21 at 16:14
 2019-03-21, 16:26 #5 a1call     "Rashid Naimi" Oct 2015 Remote to Here/There 27·17 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 2019-03-21 at 16:28
 2019-03-21, 16:36 #6 danaj   "Dana Jacobsen" Feb 2011 Bangkok, TH 38D16 Posts Good point. The sources don't even include a range for a in the theorems so they side-step it that way. Only when one has to actually go implement something to *find* a suitable value does this come up.

 Similar Threads Thread Thread Starter Forum Replies Last Post a1call PARI/GP 11 2018-08-26 09:39 Trilo Miscellaneous Math 25 2018-03-11 23:20 Mr. P-1 Math 6 2009-05-31 20:03 T.Rex Math 0 2004-10-26 21:37 CMOSMIKE Math 5 2002-09-06 18:46

All times are UTC. The time now is 23:00.

Wed Dec 8 23:00:23 UTC 2021 up 138 days, 17:29, 0 users, load averages: 1.41, 1.52, 1.53