Implement the Lucas-V ("vpsp") check in the Lucas test

[fjarri]

Baillie et al¹ introduce another condition that can be checked in the Lucas test (Eq. 2, and later Def. 7). They report it leading to very few false positives compared to the original Lucas part of the Baillie-PSW test. Need to see if implementing it slows down the test significantly; if it does, we can make it optional.

Also it kind of resembles the already implemented "extra strong check".

Footnotes

1. 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]

Added in 3ce6cf8

[fjarri]

Actually, in my tests Lucas-V seems to be a little faster in general (both when generating a random prime, and for testing a specific known prime). I assume it has something to do with the relative cost of operations (multiplication, inversion, Montgomery conversion) in Mathematica compared to the Rust library I'm using. It may even be sped up more by implementing some optimizations mentioned in #2.

[fjarri]

@ValZapod , I just noticed that in the link you posted they didn't find any pseudoprimes for Lucas-V under 10 million, but there should be one - 913 (see the paper referenced in the beginning of this issue). I wonder what is causing it.

Edit: ah, I see, they include U = 0 congruence check. In that case my timing estimate would be different since this library does not currently support doing both U and V checks.

[fjarri]

Yes, this is the U check I'm referring to. I think I stopped at just implementing the V check out of curiosity because I was more concerned with following the FIPS standard. But I see that later in the paper they advocate for combining U and V checks. This would make the test slower. The item 1 from #2 can be revisited if there's some efficient way to divide by 2 in Montgomery representation.

[fjarri]

Hm, actually it seems that just the division by 2 in the Montgomery form should work fine. So #2 can definitely be revisited.