Implement both methods for doing Lucas probable prime tests

[wbhart]

The three values 209, 589, and 629 are passed as Lucas pseudoprimes, whereas by the standard definition of such, they are not.

They in fact make it all the way through to the last line of the test, with parameter Q = 2. So possibly the Lucas chains are not computed correctly.

This may not be a bug, but it would be useful to understand why this happens. It makes no difference to the primality testing in flint, but may be annoying to people if it unnecessarily declares values Lucas pseudoprimes when they are not.

Part of the problem is that we have not been able to track down the exact reference for the algorithm as implemented. Is it a meld of Crandall-Pomerance and Baillie-Wagstaff?

[wbhart]

I think that parameters P = 1 and Q = (1 - D)/4 are picked as per Baillie-Wagstaff, but then treated as per parameters a, b of Crandall and Pomerance. The first step there is to compute A = a^2b^-1 - 2 mod n. Then the Lucas sequence starting with (2, A) is used.

But this is not the same as starting with (2, P) as per Baillie-Wagstaff and computing Lucas sequences with parameters P, Q.

I've no idea if this is "valid". It might be rather meaningless.

[wbhart]

Actually, Crandall-Pomerance have Delta = a^2 - 4b = 1 - (1 - D) = D. They then compute m = (n - jacobi(Delta/n))/2, which with the Baillie-Wagstaff choice yields m = (n + 1)/2.

Assuming that is actually used as the length of the Lucas sequence, then this is actually correct according to Crandall-Pomerance.

I don't know there is any reason to suppose that the Crandall-Pomerance method should lead to the same pseudoprimes as the Baillie-Wagstaff method, even with a, b chosen in this way. It's also not clear if there is any point in choosing the parameters this way.

So, I think I can now plausibly reconstruct how we got to this point. My student implemented the Crandall-Pomerance method, then discovered that the Baillie-PSW test (the one with $620 attached) requires the parameters to be chosen as per Baillie's method A. He wonders what the link is between the parameters P, Q, D defined there and the parameters a, b, Delta his implementation of Crandall-Pomerance takes. He guesses D = Delta, a = 1 and the rest follows.

Given this, it probably makes sense to amend the implementation in a later version of flint to accept a, b as per Crandall-Pomerance, with a separate version using the Baillie method A parameters for use in the Baillie-PSW test (which will then have to be checked against the Feitsma/Galway databases again, to make sure we don't screw up the primality testing in flint).

[danaj]

Thanks for all the research on this!

I have not used the Crandall-Pomerance 3.6.9 Lucas test, but I have taken advantage of their pointing out in 3.13 how to get U_m from Vm and V{m+1}. The nice thing about their algorithm is that the loop only calculates V. It is possible to add optimizations to the "standard" U/V Lucas calculations to arrive at close the that number of operations. What is missing from C-P (in my reading) is a standard way to select the parameters. This is similar to Grantham's notes about extra strong Lucas pseudoprimes -- no discussion was made of parameter selection.

So, I believe you are correct that these are Lucas pseudoprimes, just with different parameters. It may be that there is a way to convert the Selfridge P/Q values to an appropriate a/b for algorithm 3.6.9.

NIST, in FIPS 186-4, specifies the Lucas test using the Selfridge parameters and what looks like a standard Lucas test (e.g. OEIS A217120). This is just pointing out a contemporary reference that wants this method used for BPSW, albeit their application is much larger inputs.

The strong Lucas-Selfridge test (OEIS217255) creates a subset of the Lucas-Selfridge pseudoprimes, and is usually faster because it may reduce the number of loop iterations.

Going beyond that, there is the extra strong test using the simple Baillie parameter method (OEIS217719). I like this method, but it doesn't get used as often as the (standard/strong) Lucas-Selfridge, and the pseudoprimes are not a subset. Pari uses a slightly weakened version of the extra strong test with a subtly different parameter selection (note their code doesn't match their documentation).