search

entropyxyz / crypto-primes

Random prime generation and primality testing library based on `crypto-bigint`.
https://docs.rs/crypto-primes
Apache License 2.0
17 stars 4 forks source link

Is `gcd(Q, n)` required in the Lucas test? #1

Closed fjarri closed 1 year ago

fjarri commented 1 year ago

Baillie & Wagstaff[^Baillie1980] 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 paper[^Baillie2021], 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.

[^Baillie1980]: R. Baillie, S. S. Wagstaff, "Lucas pseudoprimes", Math. Comp. 35 1391-1417 (1980), DOI: 10.2307/2006406, http://mpqs.free.fr/LucasPseudoprimes.pdf

[^Baillie2021]: R. Baillie, A. Fiori, S. S. Wagstaff, "Strengthening the Baillie-PSW primality test", Math. Comp. 90 1931-1955 (2021), DOI: 10.1090/mcom/3616

fjarri commented 1 year ago

@dabo I wonder if you could help with this.