Implement full improved Baillie-PSW test
fjarri opened this issue · 0 comments
fjarri commented
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.