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

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

Closed fjarri closed 1 year ago

fjarri commented 1 year ago

Baillie et al[^Baillie2021] 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".

[^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

Added in 3ce6cf85e4d1b9cdc174f2f5827693619c7c7b51

fjarri commented 1 year ago

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 commented 1 year ago

@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 commented 1 year ago

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 commented 1 year ago

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