Editing Lucas primality test

{{Short description|Algorithm for checking if a number is prime}}
{{for multi|the test for Mersenne numbers|Lucas–Lehmer primality test|the Lucas–Lehmer–Riesel test|Lucas–Lehmer–Riesel test|the Lucas probable prime test|Lucas pseudoprime}}

In [[computational number theory]], the '''Lucas test''' is a [[primality test]] for a natural number ''n''; it requires that the [[prime factors]] of ''n'' &minus; 1 be already known.<ref>{{cite book |last1=Crandall |first1=Richard |last2=Pomerance |first2=Carl
 |title=Prime Numbers: a Computational Perspective
|year=2005|publisher=Springer|isbn=0-387-25282-7 |page=173 |edition=2nd }}</ref><ref>{{cite book |last1=Křížek |first1=Michal |last2=Luca |first2=Florian |last3=Somer |first3=Lawrence |title=17 Lectures on Fermat Numbers: From Number Theory to Geometry  |series=CMS Books in Mathematics |volume= 9|year=2001|publisher=Canadian Mathematical Society/Springer|isbn=0-387-95332-9 |page=41}}</ref> It is the basis of the [[Pratt certificate]] that gives a concise verification that ''n'' is prime.

==Concepts==
Let ''n'' be a positive integer.  If  there exists an integer ''a'', 1&nbsp;<&nbsp;''a''&nbsp;<&nbsp;''n'', such that

:<math>a^{n-1}\ \equiv\ 1 \pmod n \, </math>

and for every prime factor ''q'' of ''n''&nbsp;&minus;&nbsp;1

:<math>a^{({n-1})/q}\ \not\equiv\ 1 \pmod n \, </math>

then ''n'' is prime. If no such number ''a'' exists, then ''n'' is either 1, 2, or [[composite number|composite]].

The reason for the correctness of this claim is as follows: if the first equivalence holds for ''a'', we can deduce that ''a'' and ''n'' are [[coprime#Properties|coprime]]. If ''a'' also survives the second step, then the [[Order (group theory)|order]] of ''a'' in the [[Group (mathematics)|group]] ('''Z'''/''n'''''Z''')* is equal to ''n''&minus;1, which means that the order of that group  is ''n''&minus;1 (because the order of every element of a group divides the order of the group), implying that ''n'' is [[Prime number|prime]]. Conversely, if ''n'' is prime, then there exists a [[primitive root modulo n|primitive root modulo ''n'']], or [[generating set of a group|generator]] of the group ('''Z'''/''n'''''Z''')*. Such a generator has order |('''Z'''/''n'''''Z''')*|&nbsp;=&nbsp;''n''&minus;1 and both equivalences will hold for any such primitive root.

Note that if there exists an ''a''&nbsp;<&nbsp;''n'' such that the first equivalence fails, ''a'' is called a [[Fermat primality test#Concept|Fermat witness]] for the compositeness of ''n''.

==Example==
For example, take ''n'' = 71. Then ''n''&nbsp;&minus;&nbsp;1 = 70 and the prime factors of 70 are 2, 5 and 7.
We randomly select an ''a=17''&nbsp;<&nbsp;''n''. Now we compute:

:<math>17^{70}\ \equiv\ 1 \pmod {71}.</math>

For all integers ''a'' it is known that

:<math>a^{n - 1}\equiv 1 \pmod{n}\ \text{  if and only if } \text{ ord}(a)|(n-1).</math>

Therefore, the [[multiplicative order]] of 17 (mod 71) is not necessarily 70 because some factor of 70 may also work above. So check 70 divided by its prime factors:

:<math>17^{35}\ \equiv\ 70\ \not\equiv\ 1 \pmod {71}</math>

:<math>17^{14}\ \equiv\ 25\ \not\equiv\ 1 \pmod {71}</math>

:<math>17^{10}\ \equiv\ 1\ \equiv\ 1 \pmod {71}.</math>

Unfortunately, we get that 17<sup>10</sup>&equiv;1 (mod 71). So we still don't know if 71 is prime or not.

We try another random ''a'', this time choosing ''a''&nbsp;=&nbsp;11. Now we compute:

:<math>11^{70}\ \equiv\ 1 \pmod {71}.</math>

Again, this does not show that the multiplicative order of 11 (mod 71) is 70 because some factor of 70 may also work. So check 70 divided by its prime factors:

:<math>11^{35}\ \equiv\ 70\ \not\equiv\ 1 \pmod {71}</math>

:<math>11^{14}\ \equiv\ 54\ \not\equiv\ 1 \pmod {71}</math>

:<math>11^{10}\ \equiv\ 32\ \not\equiv\ 1 \pmod {71}.</math>

So the multiplicative order of 11 (mod 71) is 70, and thus 71 is prime.

(To carry out these [[modular exponentiation]]s, one could use a fast exponentiation algorithm like [[Exponentiation by squaring|binary]] or [[addition-chain exponentiation]]).

==Algorithm==
The algorithm can be written in [[pseudocode]] as follows:

 '''algorithm''' lucas_primality_test '''is'''
     '''input''': ''n'' > 2, an odd integer to be tested for primality.
            ''k'', a parameter that determines the accuracy of the test.
     '''output''': ''prime'' if ''n'' is prime, otherwise ''composite'' or ''possibly composite''.
 
     determine the prime factors of ''n''&minus;1.
 
     LOOP1: '''repeat''' ''k'' times:
         pick ''a'' randomly in the range [2, ''n'' − 1]
             {{nowrap|'''if''' <math>a^{n-1} \not\equiv 1 \pmod n</math> '''then'''}}
                 '''return''' ''composite''
             '''else''' {{nowrap|{{color|gray|#}} <math>\color{Gray}{a^{n-1} \equiv 1 \pmod n}</math>}}
                 LOOP2: '''for''' all prime factors ''q'' of ''n''&minus;1:
                     {{nowrap|'''if''' <math>a^\frac{n-1}q \not\equiv 1 \pmod n</math> '''then'''}}
                         '''if''' we checked this equality for all prime factors of ''n''&minus;1 '''then'''
                             '''return''' ''prime''
                         '''else'''
                             '''continue''' LOOP2
                     '''else''' {{nowrap|{{color|gray|#}} <math>\color{Gray}{a^\frac{n-1}q \equiv 1 \pmod n}</math>}}
                         '''continue''' LOOP1
 
     '''return''' ''possibly composite''.

== See also ==
* [[Édouard Lucas]], for whom this test is named
* [[Fermat's little theorem]]
* [[Pocklington primality test]], an improved version of this test which only requires a partial factorization of ''n''&nbsp;−&nbsp;1
* [[Primality certificate]]

==Notes==
{{Reflist}}

{{number theoretic algorithms}}

[[Category:Primality tests]]