blob: d9a5f1ec968384016189882a7eea612e94eec051 [file] [log] [blame]
 // Copyright 2016 The Go Authors. All rights reserved. // Use of this source code is governed by a BSD-style // license that can be found in the LICENSE file. package big import "math/rand" // 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 { // Note regarding the doc comment above: // It would be more precise to say that the Baillie-PSW test uses the // extra strong Lucas test as its Lucas test, but since no one knows // how to tell any of the Lucas tests apart inside a Baillie-PSW test // (they all work equally well empirically), that detail need not be // documented or implicitly guaranteed. // The comment does avoid saying "the" Baillie-PSW test // because of this general ambiguity. if n < 0 { panic("negative n for ProbablyPrime") } if x.neg || len(x.abs) == 0 { return false } // primeBitMask records the primes < 64. const primeBitMask uint64 = 1<<2 | 1<<3 | 1<<5 | 1<<7 | 1<<11 | 1<<13 | 1<<17 | 1<<19 | 1<<23 | 1<<29 | 1<<31 | 1<<37 | 1<<41 | 1<<43 | 1<<47 | 1<<53 | 1<<59 | 1<<61 w := x.abs if len(x.abs) == 1 && w < 64 { return primeBitMask&(1< 10000 { // This is widely believed to be impossible. // If we get a report, we'll want the exact number n. panic("math/big: internal error: cannot find (D/n) = -1 for " + intN.String()) } d = p*p - 4 j := Jacobi(intD, intN) if j == -1 { break } if j == 0 { // d = p²-4 = (p-2)(p+2). // If (d/n) == 0 then d shares a prime factor with n. // Since the loop proceeds in increasing p and starts with p-2==1, // the shared prime factor must be p+2. // If p+2 == n, then n is prime; otherwise p+2 is a proper factor of n. return len(n) == 1 && n == p+2 } if p == 40 { // We'll never find (d/n) = -1 if n is a square. // If n is a non-square we expect to find a d in just a few attempts on average. // After 40 attempts, take a moment to check if n is indeed a square. t1 = t1.sqrt(n) t1 = t1.sqr(t1) if t1.cmp(n) == 0 { return false } } } // Grantham definition of "extra strong Lucas pseudoprime", after Thm 2.3 on p. 876 // (D, P, Q above have become Δ, b, 1): // // Let U_n = U_n(b, 1), V_n = V_n(b, 1), and Δ = b²-4. // An extra strong Lucas pseudoprime to base b is a composite n = 2^r s + Jacobi(Δ, n), // where s is odd and gcd(n, 2*Δ) = 1, such that either (i) U_s ≡ 0 mod n and V_s ≡ ±2 mod n, // or (ii) V_{2^t s} ≡ 0 mod n for some 0 ≤ t < r-1. // // We know gcd(n, Δ) = 1 or else we'd have found Jacobi(d, n) == 0 above. // We know gcd(n, 2) = 1 because n is odd. // // Arrange s = (n - Jacobi(Δ, n)) / 2^r = (n+1) / 2^r. s := nat(nil).add(n, natOne) r := int(s.trailingZeroBits()) s = s.shr(s, uint(r)) nm2 := nat(nil).sub(n, natTwo) // n-2 // We apply the "almost extra strong" test, which checks the above conditions // except for U_s ≡ 0 mod n, which allows us to avoid computing any U_k values. // Jacobsen points out that maybe we should just do the full extra strong test: // "It is also possible to recover U_n using Crandall and Pomerance equation 3.13: // U_n = D^-1 (2V_{n+1} - PV_n) allowing us to run the full extra-strong test // at the cost of a single modular inversion. This computation is easy and fast in GMP, // so we can get the full extra-strong test at essentially the same performance as the // almost extra strong test." // Compute Lucas sequence V_s(b, 1), where: // // V(0) = 2 // V(1) = P // V(k) = P V(k-1) - Q V(k-2). // // (Remember that due to method C above, P = b, Q = 1.) // // In general V(k) = α^k + β^k, where α and β are roots of x² - Px + Q. // Crandall and Pomerance (p.147) observe that for 0 ≤ j ≤ k, // // V(j+k) = V(j)V(k) - V(k-j). // // So in particular, to quickly double the subscript: // // V(2k) = V(k)² - 2 // V(2k+1) = V(k) V(k+1) - P // // We can therefore start with k=0 and build up to k=s in log₂(s) steps. natP := nat(nil).setWord(p) vk := nat(nil).setWord(2) vk1 := nat(nil).setWord(p) t2 := nat(nil) // temp for i := int(s.bitLen()); i >= 0; i-- { if s.bit(uint(i)) != 0 { // k' = 2k+1 // V(k') = V(2k+1) = V(k) V(k+1) - P. t1 = t1.mul(vk, vk1) t1 = t1.add(t1, n) t1 = t1.sub(t1, natP) t2, vk = t2.div(vk, t1, n) // V(k'+1) = V(2k+2) = V(k+1)² - 2. t1 = t1.sqr(vk1) t1 = t1.add(t1, nm2) t2, vk1 = t2.div(vk1, t1, n) } else { // k' = 2k // V(k'+1) = V(2k+1) = V(k) V(k+1) - P. t1 = t1.mul(vk, vk1) t1 = t1.add(t1, n) t1 = t1.sub(t1, natP) t2, vk1 = t2.div(vk1, t1, n) // V(k') = V(2k) = V(k)² - 2 t1 = t1.sqr(vk) t1 = t1.add(t1, nm2) t2, vk = t2.div(vk, t1, n) } } // Now k=s, so vk = V(s). Check V(s) ≡ ±2 (mod n). if vk.cmp(natTwo) == 0 || vk.cmp(nm2) == 0 { // Check U(s) ≡ 0. // As suggested by Jacobsen, apply Crandall and Pomerance equation 3.13: // // U(k) = D⁻¹ (2 V(k+1) - P V(k)) // // Since we are checking for U(k) == 0 it suffices to check 2 V(k+1) == P V(k) mod n, // or P V(k) - 2 V(k+1) == 0 mod n. t1 := t1.mul(vk, natP) t2 := t2.shl(vk1, 1) if t1.cmp(t2) < 0 { t1, t2 = t2, t1 } t1 = t1.sub(t1, t2) t3 := vk1 // steal vk1, no longer needed below vk1 = nil _ = vk1 t2, t3 = t2.div(t3, t1, n) if len(t3) == 0 { return true } } // Check V(2^t s) ≡ 0 mod n for some 0 ≤ t < r-1. for t := 0; t < r-1; t++ { if len(vk) == 0 { // vk == 0 return true } // Optimization: V(k) = 2 is a fixed point for V(k') = V(k)² - 2, // so if V(k) = 2, we can stop: we will never find a future V(k) == 0. if len(vk) == 1 && vk == 2 { // vk == 2 return false } // k' = 2k // V(k') = V(2k) = V(k)² - 2 t1 = t1.sqr(vk) t1 = t1.sub(t1, natTwo) t2, vk = t2.div(vk, t1, n) } return false }