probably_prime is skipping lots of primes, including primes below 2⁶⁴

[darconeous]

From the documentation for probably_prime:

ProbablyPrime is 100% accurate for inputs less than 2⁶⁴. See Menezes et al., Handbook of Applied Cryptography, 1997, pp. 145-149, and FIPS 186-4 Appendix F for further discussion of the error probabilities.

I have found counterexamples which show this assertion to be false:

assert!(probably_prime(&BigUint::from_u64(1579751).unwrap(), 20));
assert!(probably_prime(&BigUint::from_u64(1884791).unwrap(), 20));
assert!(probably_prime(&BigUint::from_u64(3818929).unwrap(), 20));
assert!(probably_prime(&BigUint::from_u64(4080359).unwrap(), 20));
assert!(probably_prime(&BigUint::from_u64(4145951).unwrap(), 20));

All 5 of these prime numbers are lower than 2⁶⁴, yet none cause probably_prime to return true.

[dignifiedquire]

The algorithm is based on the implementation in math/big from golang, including the reference. So it would be good to check if there is an issue in either the original algorithm, the go implementation, or just this implementation.

[darconeous]

Looks like it works fine in Go: https://go.dev/play/p/IfJc2JqaCjL

[dignifiedquire]

Thanks for checking, that is not good.

[dignifiedquire]

@darconeous I have a fix, at least for the primes you posted in #54

[darconeous]

In my initial testing, this seems to be performing much, much better. The output now looks equivalent to OpenSSL's BN_is_prime function.

[dignifiedquire]

Thanks a lot for reporting and testing!