Function num_bigint_dig::prime::probably_prime
source · pub fn probably_prime(x: &BigUint, n: usize) -> bool
Expand description
ProbablyPrime reports whether x is probably prime, applying the Miller-Rabin test with n pseudorandomly chosen bases as well as a Baillie-PSW test.
If x is prime, ProbablyPrime returns true. If x is chosen randomly and not prime, ProbablyPrime probably returns false. The probability of returning true for a randomly chosen non-prime is at most ¼ⁿ.
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.
ProbablyPrime is not suitable for judging primes that an adversary may have crafted to fool the test.
This is a port of ProbablyPrime
from the go std lib.