-
Notifications
You must be signed in to change notification settings - Fork 17.8k
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
big.ProbablyPrime returns false negatives #638
Labels
Comments
->agl for a closer look, if you have time. Looks like this could be the root cause: big.ProbablyPrime(18699199384836356663) = false, should be true. --- package main import "big" func main() { z := big.NewInt(0) z.SetString("18699199384836356663", 10) println(z.String()) println(big.ProbablyPrime(z, 20)) // prints false, both 8g and 6g } --- http://www.wolframalpha.com/input/?i=18699199384836356663 says that it is prime. Labels changed: added packagebug. Owner changed to a...@golang.org. Status changed to Accepted. |
I believe the slowness could be due to the incorrectness of the algorithm. I have a couple of examples in the 648-bit space where it takes 108k tries before a random is reached (all-in-all covering 216000 different numbers); another, in the 66-bit space and using the incremental algorithm, fails to find a prime in at least the 12,630,912 numbers between 18699199384836273063 and 18699199384848903975. p9p's probable_prime finds 4225 primes within that slice, and wolfram alpha confirms at least a dozen of (somewhat) random sampled finds from there. let me know if you want the file with the odd numbers (stepping of 4) of that slice for testing. |
(removing the RSA speed from consideration) There were a couple of issues with probablyPrime. I've written a couple of test programs that use GMP to verify ProbablyPrime and they've now run for several million iterations of 512 bit numbers with no problems. CL coming in a sec. Attachments: |
This issue was closed by revision 308064f. Status changed to Fixed. |
This issue was closed.
Sign up for free
to subscribe to this conversation on GitHub.
Already have an account?
Sign in.
The text was updated successfully, but these errors were encountered: