// 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. // // As of Go 1.8, ProbablyPrime(0) is allowed and applies only a Baillie-PSW test. // Before Go 1.8, ProbablyPrime applied only the Miller-Rabin tests, and ProbablyPrime(0) panicked. func (x *Int) ProbablyPrime(n int) bool { … } // probablyPrimeMillerRabin reports whether n passes reps rounds of the // Miller-Rabin primality test, using pseudo-randomly chosen bases. // If force2 is true, one of the rounds is forced to use base 2. // See Handbook of Applied Cryptography, p. 139, Algorithm 4.24. // The number n is known to be non-zero. func (n nat) probablyPrimeMillerRabin(reps int, force2 bool) bool { … } // probablyPrimeLucas reports whether n passes the "almost extra strong" Lucas probable prime test, // using Baillie-OEIS parameter selection. This corresponds to "AESLPSP" on Jacobsen's tables (link below). // The combination of this test and a Miller-Rabin/Fermat test with base 2 gives a Baillie-PSW test. // // References: // // Baillie and Wagstaff, "Lucas Pseudoprimes", Mathematics of Computation 35(152), // October 1980, pp. 1391-1417, especially page 1401. // https://www.ams.org/journals/mcom/1980-35-152/S0025-5718-1980-0583518-6/S0025-5718-1980-0583518-6.pdf // // Grantham, "Frobenius Pseudoprimes", Mathematics of Computation 70(234), // March 2000, pp. 873-891. // https://www.ams.org/journals/mcom/2001-70-234/S0025-5718-00-01197-2/S0025-5718-00-01197-2.pdf // // Baillie, "Extra strong Lucas pseudoprimes", OEIS A217719, https://oeis.org/A217719. // // Jacobsen, "Pseudoprime Statistics, Tables, and Data", http://ntheory.org/pseudoprimes.html. // // Nicely, "The Baillie-PSW Primality Test", https://web.archive.org/web/20191121062007/http://www.trnicely.net/misc/bpsw.html. // (Note that Nicely's definition of the "extra strong" test gives the wrong Jacobi condition, // as pointed out by Jacobsen.) // // Crandall and Pomerance, Prime Numbers: A Computational Perspective, 2nd ed. // Springer, 2005. func (n nat) probablyPrimeLucas() bool { … }
Codebase Browser
go