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.
This is a follow-up to #3. The same paper proposes an improved BPSW test (Section 6). The test consists of:
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:
lucas_test()that would allow one to reach the last step, so not sure how it should be tested.lucas_test()since if "New-BPSW" is active, strong Lucas check cannot terminate prematurely anymore. But maybe it won't be too bad.