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

Upgrade Miller-Rabin primality test to improve accuracy. #3

Open
tfdahlin opened this issue Jul 10, 2019 · 1 comment
Open

Upgrade Miller-Rabin primality test to improve accuracy. #3

tfdahlin opened this issue Jul 10, 2019 · 1 comment

Comments

@tfdahlin
Copy link
Member

Certain composite integers have a very large quantity of non-witnesses, which means more tests are required to confirm they are indeed composite. If we can more quickly identify these numbers, it means our primality tests for certain composite numbers will end more quickly, effectively speeding up our primality testing in general. Implementation of this might be non-trivial though, as I haven't finished reading the paper yet.

Reference: Improving the Speed and Accuracy of the Miller-Rabin Primality Test

@tfdahlin tfdahlin self-assigned this Jul 10, 2019
@tfdahlin tfdahlin changed the title Upgrade Miller-Rabin primality test to improve efficiency. Upgrade Miller-Rabin primality test to improve accuracy. Jul 16, 2019
@tfdahlin
Copy link
Member Author

I might also look at implementing Baillie-PSW primality testing instead, but I can't seem to find anything that compares the two.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

No branches or pull requests

1 participant