Is `gcd(Q, n)` required in the Lucas test?
fjarri opened this issue · 1 comments
Baillie & Wagstaff1 mention right after definition of "strong pseudoprime", on p. 1396: "Every prime n satisfies the conditions ... provided (n, 2QD) = 1. But then in the next paragraph they prove that if n is a strong pseudoprime, (n, 2QD) = 1.
In a later paper2, it is a little more clear: in Section 1 it says that if (n, Q) = 1 and n is prime, then certain Lucas congruences (which we use in the test) hold. But the (n, Q) = 1 requirement does not seem to be needed for the reversed statement (if the congruences hold, then n is (probably) prime, which constitutes the Lucas test).
So does (n, Q) = 1 somehow always hold by construction, and it is so simple they decided not to even mention it? Or is it not required in the reversed statement? The lack of this check does not seem to affect the effectiveness of the Lucas test, which, in particular, produces the expected false positives up to n = 500000.
Footnotes
-
R. Baillie, S. S. Wagstaff, "Lucas pseudoprimes",
Math. Comp. 35 1391-1417 (1980),
DOI: 10.2307/2006406,
http://mpqs.free.fr/LucasPseudoprimes.pdf ↩ -
R. Baillie, A. Fiori, S. S. Wagstaff,
"Strengthening the Baillie-PSW primality test",
Math. Comp. 90 1931-1955 (2021),
DOI: 10.1090/mcom/3616 ↩