entropyxyz/crypto-primes

Implement full improved Baillie-PSW test

fjarri opened this issue · 0 comments

This is a follow-up to #3. The same paper proposes an improved BPSW test (Section 6). The test consists of:

  • MR test with base 2
  • Lucas base A* (the base selection can uncover the candidate to be composite; see the paper for details)
  • Strong Lucas check
  • Lucas-V check
  • Check that Q^((n+1)/2) == Q * Jacobi(Q, n) (using the powers of Q already calculated during the Lucas test)

This can be made a separate preset.

Problems:

  • There don't seem to be any inputs to lucas_test() that would allow one to reach the last step, so not sure how it should be tested.
  • Complicates the check structure in lucas_test() since if "New-BPSW" is active, strong Lucas check cannot terminate prematurely anymore. But maybe it won't be too bad.