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 Miller-Rabin primality testing for prime-related functions #86

Open
Mego opened this issue Oct 18, 2017 · 3 comments
Open

Implement Miller-Rabin primality testing for prime-related functions #86

Mego opened this issue Oct 18, 2017 · 3 comments

Comments

@Mego
Copy link
Owner

Mego commented Oct 18, 2017

Ideally, this will be a standalone implementation - no reliance on numpy or sympy. I'd like to avoid adding those as requirements, as they're quite large libraries.

The implementation must be deterministic.

Bonus points for using the current-best set of witnesses to ensure accuracy for very large numbers.

@misingnoglic
Copy link
Contributor

On it :)

@Mego
Copy link
Owner Author

Mego commented Oct 20, 2017

Next step: using MR for primality testing for the prime-related commands. I'll work on this :)

@Mego
Copy link
Owner Author

Mego commented Oct 20, 2017

@misingnoglic As I mentioned on the PR that I prematurely merged, the implementation you wrote does not meet the requirements, because it is not a deterministic implementation.

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

2 participants