Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Implement full improved Baillie-PSW test #21

Open
fjarri opened this issue Apr 21, 2023 · 0 comments
Open

Implement full improved Baillie-PSW test #21

fjarri opened this issue Apr 21, 2023 · 0 comments
Labels
enhancement New feature or request

Comments

@fjarri
Copy link
Member

fjarri commented Apr 21, 2023

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.
@fjarri fjarri added the enhancement New feature or request label Apr 21, 2023
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
enhancement New feature or request
Projects
None yet
Development

No branches or pull requests

1 participant