Editing Lucas pseudoprime (section)

== Baillie-Wagstaff-Lucas pseudoprimes ==

Baillie and Wagstaff define Lucas pseudoprimes as follows:<ref name="lpsp">{{cite journal |author1 = Robert Baillie |author2 = Samuel S. Wagstaff, Jr. |author-link2 = Samuel S. Wagstaff, Jr. |title=Lucas Pseudoprimes |journal=Mathematics of Computation |date=October 1980 |volume=35 |issue=152 |pages=1391–1417 |url=http://mpqs.free.fr/LucasPseudoprimes.pdf |mr=583518 |jstor=2006406 |doi=10.1090/S0025-5718-1980-0583518-6 |doi-access=free }}</ref> Given integers ''P'' and ''Q'', where ''P'' > 0 and <math>D=P^2-4Q</math>,
let ''U<sub>k</sub>''(''P'', ''Q'') and ''V<sub>k</sub>''(''P'', ''Q'') be the corresponding [[Lucas sequence]]s.

Let ''n'' be a positive integer and let <math>\left(\tfrac{D}{n}\right)</math> be the [[Jacobi symbol]]. We define

: <math>\delta(n)=n-\left(\tfrac{D}{n}\right).</math>

If ''n'' is a [[prime number|prime]] that does not divide ''Q'', then the following congruence condition holds:

{{NumBlk|:|<math>U_{\delta(n)} \equiv 0 \pmod {n}.</math>|{{EquationRef|1}}}}

If this congruence does ''not'' hold, then ''n'' is ''not'' prime.
If ''n'' is ''composite'', then this congruence ''usually'' does not hold.<ref name="lpsp"/> These are the key facts that make Lucas sequences useful in [[primality test]]ing.

The congruence ({{EquationNote|1}}) represents one of two congruences defining a [[Frobenius pseudoprime]]. Hence, every Frobenius pseudoprime is also a Baillie-Wagstaff-Lucas pseudoprime, but the converse does not always hold.

Some good references are chapter 8 of the book by Bressoud and Wagon (with [[Mathematica]] code),<ref name="Bressoud">
{{cite book | author = David Bressoud | author-link = David Bressoud | author2 = Stan Wagon | author-link2 = Stan Wagon | title = A Course in Computational Number Theory | publisher = Key College Publishing in cooperation with Springer | location = New York | year = 2000 | isbn = 978-1-930190-10-8 | url-access = registration | url = https://archive.org/details/courseincomputat0000bres }}
</ref> pages 142–152 of the book by Crandall and Pomerance,<ref name="CrandallPomerance">
{{cite book | title=Prime numbers: A computational perspective | edition=2nd | author=Richard E. Crandall | author-link=Richard Crandall |author2=Carl Pomerance |author-link2=Carl Pomerance | publisher=[[Springer-Verlag]] | year=2005 | isbn=0-387-25282-7}}
</ref> and pages 53–74 of the book by Ribenboim.<ref name="Ribenboim">
{{cite book | title=The New Book of Prime Number Records | author=Paulo Ribenboim |author-link=Paulo Ribenboim | publisher=[[Springer-Verlag]] | year=1996 | isbn=0-387-94457-5 }}
</ref>