Editing Lucas pseudoprime (section)

==Lucas probable primes and pseudoprimes==

A '''Lucas probable prime''' for a given (''P, Q'') pair is ''any'' positive integer ''n'' for which equation ({{EquationNote|1}}) above is true (see,<ref name="lpsp"/> page 1398).

A '''Lucas pseudoprime''' for a given (''P, Q'') pair is a positive ''composite'' integer ''n'' for which equation ({{EquationNote|1}}) is true (see,<ref name="lpsp"/> page 1391).

A Lucas probable prime test is most useful if ''D'' is chosen such that the Jacobi symbol <math>\left(\tfrac{D}{n}\right)</math> is &minus;1
(see pages 1401–1409 of,<ref name="lpsp"/> page 1024 of,<ref name="PSW">{{cite journal |author1 = Carl Pomerance |author-link1 = Carl Pomerance |author2 = John L. Selfridge |author-link2 = John L. Selfridge |author3 = Samuel S. Wagstaff, Jr. |author-link3 = Samuel S. Wagstaff, Jr. |title=The pseudoprimes to 25·10<sup>9</sup> |journal=Mathematics of Computation |date=July 1980 |volume=35 |issue=151 |pages=1003–1026 |url=//math.dartmouth.edu/~carlp/PDF/paper25.pdf |jstor=2006210 |doi=10.1090/S0025-5718-1980-0572872-7 |doi-access=free }}</ref> or pages 266–269 of <ref name="Bressoud"/>
).  This is especially important when combining a Lucas test with a [[strong pseudoprime]] test, such as the [[Baillie–PSW primality test]].  Typically implementations will use a parameter selection method that ensures this condition (e.g. the Selfridge method recommended in <ref name="lpsp"/> and described below).

If <math>\left(\tfrac{D}{n}\right)=-1,</math> then equation ({{EquationNote|1}}) becomes
{{NumBlk|:|<math>U_{n+1} \equiv 0 \pmod {n}.</math>|{{EquationRef|2}}}}

If congruence ({{EquationNote|2}}) is false, this constitutes a proof that ''n'' is composite.

If congruence ({{EquationNote|2}}) is true, then ''n'' is a Lucas probable prime.
In this case, either ''n'' is prime or it is a Lucas pseudoprime.
If congruence ({{EquationNote|2}}) is true, then ''n'' is ''likely'' to be prime (this justifies the term '''probable''' prime), but this does not ''prove'' that ''n'' is prime.
As is the case with any other probabilistic primality test, if we perform additional Lucas tests with different ''D'', ''P'' and ''Q'', then unless one of the tests proves that ''n'' is composite, we gain more confidence that ''n'' is prime.

Examples: If ''P'' = 3, ''Q'' = &minus;1, and ''D'' = 13, the sequence of ''U'''s is {{oeis|id=A006190}}: ''U<sub>0</sub>'' = 0, ''U<sub>1</sub>'' = 1, ''U<sub>2</sub>'' = 3, ''U<sub>3</sub>'' = 10, etc.

First, let ''n'' = 19. The Jacobi symbol <math>\left(\tfrac{13}{19}\right)</math> is &minus;1, so  δ(''n'') = 20, ''U<sub>20</sub>'' = 6616217487 = 19·348221973 and we have
:<math> U_{20} = 6616217487 \equiv 0 \pmod {19} . </math>
Therefore, 19 is a Lucas probable prime for this (''P, Q'') pair. In this case 19 is prime, so it is ''not'' a Lucas pseudoprime.

For the next example, let ''n'' = 119. We have <math>\left(\tfrac{13}{119}\right)</math> = &minus;1, and we can compute
:<math> U_{120} \equiv 0 \pmod {119}. </math>
However, 119 = 7·17 is not prime, so 119 is a Lucas ''pseudoprime'' for this (''P, Q'') pair.
In fact, 119 is the smallest pseudoprime for ''P'' = 3, ''Q'' = &minus;1.

We will see [[Lucas pseudoprime#Implementing a Lucas probable prime test|below]] that, in order to check equation ({{EquationNote|2}}) for a given ''n'', we do ''not'' need to compute all of the first ''n'' + 1 terms in the ''U'' sequence.

Let ''Q'' = −1, the smallest Lucas pseudoprime to ''P'' = 1, 2, 3, ... are
:323, 35, 119, 9, 9, 143, 25, 33, 9, 15, 123, 35, 9, 9, 15, 129, 51, 9, 33, 15, 21, 9, 9, 49, 15, 39, 9, 35, 49, 15, 9, 9, 33, 51, 15, 9, 35, 85, 39, 9, 9, 21, 25, 51, 9, 143, 33, 119, 9, 9, 51, 33, 95, 9, 15, 301, 25, 9, 9, 15, 49, 155, 9, 399, 15, 33, 9, 9, 49, 15, 119, 9, ...