mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Reply
 
Thread Tools
Old 2019-03-21, 10:32   #1
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Out of my Body

34328 Posts
Default 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
a1call is offline   Reply With Quote
Old 2019-03-21, 11:08   #2
axn
 
axn's Avatar
 
Jun 2003

11·421 Posts
Default

Quote:
Originally Posted by a1call View Post
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).
axn is offline   Reply With Quote
Old 2019-03-21, 15:51   #3
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Out of my Body

111000110102 Posts
Default

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
a1call is offline   Reply With Quote
Old 2019-03-21, 16:12   #4
danaj
 
"Dana Jacobsen"
Feb 2011
Bangkok, TH

2·11·41 Posts
Default

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
danaj is offline   Reply With Quote
Old 2019-03-21, 16:26   #5
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Out of my Body

2×32×101 Posts
Default

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
a1call is offline   Reply With Quote
Old 2019-03-21, 16:36   #6
danaj
 
"Dana Jacobsen"
Feb 2011
Bangkok, TH

90210 Posts
Default

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.
danaj is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Lucas Primality Test in Pari GP a1call PARI/GP 11 2018-08-26 09:39
Modifying the Lucas Lehmer Primality Test into a fast test of nothing Trilo Miscellaneous Math 25 2018-03-11 23:20
The Lucas Primality Test Mr. P-1 Math 6 2009-05-31 20:03
A primality test for Fermat numbers faster than P├ępin's test ? T.Rex Math 0 2004-10-26 21:37
Lucas-Lehmer primality test CMOSMIKE Math 5 2002-09-06 18:46

All times are UTC. The time now is 08:15.

Sun Jul 5 08:15:05 UTC 2020 up 102 days, 5:48, 1 user, load averages: 1.12, 1.30, 1.25

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.