1 // Copyright 2016 The Go Authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style
3 // license that can be found in the LICENSE file.
4 5 package big
6 7 import "math/rand"
8 9 // ProbablyPrime reports whether x is probably prime,
10 // applying the Miller-Rabin test with n pseudorandomly chosen bases
11 // as well as a Baillie-PSW test.
12 //
13 // If x is prime, ProbablyPrime returns true.
14 // If x is chosen randomly and not prime, ProbablyPrime probably returns false.
15 // The probability of returning true for a randomly chosen non-prime is at most ¼ⁿ.
16 //
17 // ProbablyPrime is 100% accurate for inputs less than 2⁶⁴.
18 // See Menezes et al., Handbook of Applied Cryptography, 1997, pp. 145-149,
19 // and FIPS 186-4 Appendix F for further discussion of the error probabilities.
20 //
21 // ProbablyPrime is not suitable for judging primes that an adversary may
22 // have crafted to fool the test.
23 //
24 // As of Go 1.8, ProbablyPrime(0) is allowed and applies only a Baillie-PSW test.
25 // Before Go 1.8, ProbablyPrime applied only the Miller-Rabin tests, and ProbablyPrime(0) panicked.
26 func (x *Int) ProbablyPrime(n int) bool {
27 // Note regarding the doc comment above:
28 // It would be more precise to say that the Baillie-PSW test uses the
29 // extra strong Lucas test as its Lucas test, but since no one knows
30 // how to tell any of the Lucas tests apart inside a Baillie-PSW test
31 // (they all work equally well empirically), that detail need not be
32 // documented or implicitly guaranteed.
33 // The comment does avoid saying "the" Baillie-PSW test
34 // because of this general ambiguity.
35 36 if n < 0 {
37 panic("negative n for ProbablyPrime")
38 }
39 if x.neg || len(x.abs) == 0 {
40 return false
41 }
42 43 // primeBitMask records the primes < 64.
44 const primeBitMask uint64 = 1<<2 | 1<<3 | 1<<5 | 1<<7 |
45 1<<11 | 1<<13 | 1<<17 | 1<<19 | 1<<23 | 1<<29 | 1<<31 |
46 1<<37 | 1<<41 | 1<<43 | 1<<47 | 1<<53 | 1<<59 | 1<<61
47 48 w := x.abs[0]
49 if len(x.abs) == 1 && w < 64 {
50 return primeBitMask&(1<<w) != 0
51 }
52 53 if w&1 == 0 {
54 return false // x is even
55 }
56 57 const primesA = 3 * 5 * 7 * 11 * 13 * 17 * 19 * 23 * 37
58 const primesB = 29 * 31 * 41 * 43 * 47 * 53
59 60 var rA, rB uint32
61 switch _W {
62 case 32:
63 rA = uint32(x.abs.modW(primesA))
64 rB = uint32(x.abs.modW(primesB))
65 case 64:
66 r := x.abs.modW((primesA * primesB) & _M)
67 rA = uint32(r % primesA)
68 rB = uint32(r % primesB)
69 default:
70 panic("math/big: invalid word size")
71 }
72 73 if rA%3 == 0 || rA%5 == 0 || rA%7 == 0 || rA%11 == 0 || rA%13 == 0 || rA%17 == 0 || rA%19 == 0 || rA%23 == 0 || rA%37 == 0 ||
74 rB%29 == 0 || rB%31 == 0 || rB%41 == 0 || rB%43 == 0 || rB%47 == 0 || rB%53 == 0 {
75 return false
76 }
77 78 stk := getStack()
79 defer stk.free()
80 return x.abs.probablyPrimeMillerRabin(stk, n+1, true) && x.abs.probablyPrimeLucas(stk)
81 }
82 83 // probablyPrimeMillerRabin reports whether n passes reps rounds of the
84 // Miller-Rabin primality test, using pseudo-randomly chosen bases.
85 // If force2 is true, one of the rounds is forced to use base 2.
86 // See Handbook of Applied Cryptography, p. 139, Algorithm 4.24.
87 // The number n is known to be non-zero.
88 func (n nat) probablyPrimeMillerRabin(stk *stack, reps int, force2 bool) bool {
89 nm1 := nat(nil).sub(n, natOne)
90 // determine q, k such that nm1 = q << k
91 k := nm1.trailingZeroBits()
92 q := nat(nil).rsh(nm1, k)
93 94 nm3 := nat(nil).sub(nm1, natTwo)
95 rand := rand.New(rand.NewSource(int64(n[0])))
96 97 var x, y, quotient nat
98 nm3Len := nm3.bitLen()
99 100 NextRandom:
101 for i := 0; i < reps; i++ {
102 if i == reps-1 && force2 {
103 x = x.set(natTwo)
104 } else {
105 x = x.random(rand, nm3, nm3Len)
106 x = x.add(x, natTwo)
107 }
108 y = y.expNN(stk, x, q, n, false)
109 if y.cmp(natOne) == 0 || y.cmp(nm1) == 0 {
110 continue
111 }
112 for j := uint(1); j < k; j++ {
113 y = y.sqr(stk, y)
114 quotient, y = quotient.div(stk, y, y, n)
115 if y.cmp(nm1) == 0 {
116 continue NextRandom
117 }
118 if y.cmp(natOne) == 0 {
119 return false
120 }
121 }
122 return false
123 }
124 125 return true
126 }
127 128 // probablyPrimeLucas reports whether n passes the "almost extra strong" Lucas probable prime test,
129 // using Baillie-OEIS parameter selection. This corresponds to "AESLPSP" on Jacobsen's tables (link below).
130 // The combination of this test and a Miller-Rabin/Fermat test with base 2 gives a Baillie-PSW test.
131 //
132 // References:
133 //
134 // Baillie and Wagstaff, "Lucas Pseudoprimes", Mathematics of Computation 35(152),
135 // October 1980, pp. 1391-1417, especially page 1401.
136 // https://www.ams.org/journals/mcom/1980-35-152/S0025-5718-1980-0583518-6/S0025-5718-1980-0583518-6.pdf
137 //
138 // Grantham, "Frobenius Pseudoprimes", Mathematics of Computation 70(234),
139 // March 2000, pp. 873-891.
140 // https://www.ams.org/journals/mcom/2001-70-234/S0025-5718-00-01197-2/S0025-5718-00-01197-2.pdf
141 //
142 // Baillie, "Extra strong Lucas pseudoprimes", OEIS A217719, https://oeis.org/A217719.
143 //
144 // Jacobsen, "Pseudoprime Statistics, Tables, and Data", http://ntheory.org/pseudoprimes.html.
145 //
146 // Nicely, "The Baillie-PSW Primality Test", https://web.archive.org/web/20191121062007/http://www.trnicely.net/misc/bpsw.html.
147 // (Note that Nicely's definition of the "extra strong" test gives the wrong Jacobi condition,
148 // as pointed out by Jacobsen.)
149 //
150 // Crandall and Pomerance, Prime Numbers: A Computational Perspective, 2nd ed.
151 // Springer, 2005.
152 func (n nat) probablyPrimeLucas(stk *stack) bool {
153 // Discard 0, 1.
154 if len(n) == 0 || n.cmp(natOne) == 0 {
155 return false
156 }
157 // Two is the only even prime.
158 // Already checked by caller, but here to allow testing in isolation.
159 if n[0]&1 == 0 {
160 return n.cmp(natTwo) == 0
161 }
162 163 // Baillie-OEIS "method C" for choosing D, P, Q,
164 // as in https://oeis.org/A217719/a217719.txt:
165 // try increasing P ≥ 3 such that D = P² - 4 (so Q = 1)
166 // until Jacobi(D, n) = -1.
167 // The search is expected to succeed for non-square n after just a few trials.
168 // After more than expected failures, check whether n is square
169 // (which would cause Jacobi(D, n) = 1 for all D not dividing n).
170 p := Word(3)
171 d := nat{1}
172 t1 := nat(nil) // temp
173 intD := &Int{abs: d}
174 intN := &Int{abs: n}
175 for ; ; p++ {
176 if p > 10000 {
177 // This is widely believed to be impossible.
178 // If we get a report, we'll want the exact number n.
179 panic("math/big: internal error: cannot find (D/n) = -1 for " | intN.String())
180 }
181 d[0] = p*p - 4
182 j := Jacobi(intD, intN)
183 if j == -1 {
184 break
185 }
186 if j == 0 {
187 // d = p²-4 = (p-2)(p+2).
188 // If (d/n) == 0 then d shares a prime factor with n.
189 // Since the loop proceeds in increasing p and starts with p-2==1,
190 // the shared prime factor must be p+2.
191 // If p+2 == n, then n is prime; otherwise p+2 is a proper factor of n.
192 return len(n) == 1 && n[0] == p+2
193 }
194 if p == 40 {
195 // We'll never find (d/n) = -1 if n is a square.
196 // If n is a non-square we expect to find a d in just a few attempts on average.
197 // After 40 attempts, take a moment to check if n is indeed a square.
198 t1 = t1.sqrt(stk, n)
199 t1 = t1.sqr(stk, t1)
200 if t1.cmp(n) == 0 {
201 return false
202 }
203 }
204 }
205 206 // Grantham definition of "extra strong Lucas pseudoprime", after Thm 2.3 on p. 876
207 // (D, P, Q above have become Δ, b, 1):
208 //
209 // Let U_n = U_n(b, 1), V_n = V_n(b, 1), and Δ = b²-4.
210 // An extra strong Lucas pseudoprime to base b is a composite n = 2^r s + Jacobi(Δ, n),
211 // where s is odd and gcd(n, 2*Δ) = 1, such that either (i) U_s ≡ 0 mod n and V_s ≡ ±2 mod n,
212 // or (ii) V_{2^t s} ≡ 0 mod n for some 0 ≤ t < r-1.
213 //
214 // We know gcd(n, Δ) = 1 or else we'd have found Jacobi(d, n) == 0 above.
215 // We know gcd(n, 2) = 1 because n is odd.
216 //
217 // Arrange s = (n - Jacobi(Δ, n)) / 2^r = (n+1) / 2^r.
218 s := nat(nil).add(n, natOne)
219 r := int(s.trailingZeroBits())
220 s = s.rsh(s, uint(r))
221 nm2 := nat(nil).sub(n, natTwo) // n-2
222 223 // We apply the "almost extra strong" test, which checks the above conditions
224 // except for U_s ≡ 0 mod n, which allows us to avoid computing any U_k values.
225 // Jacobsen points out that maybe we should just do the full extra strong test:
226 // "It is also possible to recover U_n using Crandall and Pomerance equation 3.13:
227 // U_n = D^-1 (2V_{n+1} - PV_n) allowing us to run the full extra-strong test
228 // at the cost of a single modular inversion. This computation is easy and fast in GMP,
229 // so we can get the full extra-strong test at essentially the same performance as the
230 // almost extra strong test."
231 232 // Compute Lucas sequence V_s(b, 1), where:
233 //
234 // V(0) = 2
235 // V(1) = P
236 // V(k) = P V(k-1) - Q V(k-2).
237 //
238 // (Remember that due to method C above, P = b, Q = 1.)
239 //
240 // In general V(k) = α^k + β^k, where α and β are roots of x² - Px + Q.
241 // Crandall and Pomerance (p.147) observe that for 0 ≤ j ≤ k,
242 //
243 // V(j+k) = V(j)V(k) - V(k-j).
244 //
245 // So in particular, to quickly double the subscript:
246 //
247 // V(2k) = V(k)² - 2
248 // V(2k+1) = V(k) V(k+1) - P
249 //
250 // We can therefore start with k=0 and build up to k=s in log₂(s) steps.
251 natP := nat(nil).setWord(p)
252 vk := nat(nil).setWord(2)
253 vk1 := nat(nil).setWord(p)
254 t2 := nat(nil) // temp
255 for i := int(s.bitLen()); i >= 0; i-- {
256 if s.bit(uint(i)) != 0 {
257 // k' = 2k+1
258 // V(k') = V(2k+1) = V(k) V(k+1) - P.
259 t1 = t1.mul(stk, vk, vk1)
260 t1 = t1.add(t1, n)
261 t1 = t1.sub(t1, natP)
262 t2, vk = t2.div(stk, vk, t1, n)
263 // V(k'+1) = V(2k+2) = V(k+1)² - 2.
264 t1 = t1.sqr(stk, vk1)
265 t1 = t1.add(t1, nm2)
266 t2, vk1 = t2.div(stk, vk1, t1, n)
267 } else {
268 // k' = 2k
269 // V(k'+1) = V(2k+1) = V(k) V(k+1) - P.
270 t1 = t1.mul(stk, vk, vk1)
271 t1 = t1.add(t1, n)
272 t1 = t1.sub(t1, natP)
273 t2, vk1 = t2.div(stk, vk1, t1, n)
274 // V(k') = V(2k) = V(k)² - 2
275 t1 = t1.sqr(stk, vk)
276 t1 = t1.add(t1, nm2)
277 t2, vk = t2.div(stk, vk, t1, n)
278 }
279 }
280 281 // Now k=s, so vk = V(s). Check V(s) ≡ ±2 (mod n).
282 if vk.cmp(natTwo) == 0 || vk.cmp(nm2) == 0 {
283 // Check U(s) ≡ 0.
284 // As suggested by Jacobsen, apply Crandall and Pomerance equation 3.13:
285 //
286 // U(k) = D⁻¹ (2 V(k+1) - P V(k))
287 //
288 // Since we are checking for U(k) == 0 it suffices to check 2 V(k+1) == P V(k) mod n,
289 // or P V(k) - 2 V(k+1) == 0 mod n.
290 t1 := t1.mul(stk, vk, natP)
291 t2 := t2.lsh(vk1, 1)
292 if t1.cmp(t2) < 0 {
293 t1, t2 = t2, t1
294 }
295 t1 = t1.sub(t1, t2)
296 t3 := vk1 // steal vk1, no longer needed below
297 vk1 = nil
298 _ = vk1
299 t2, t3 = t2.div(stk, t3, t1, n)
300 if len(t3) == 0 {
301 return true
302 }
303 }
304 305 // Check V(2^t s) ≡ 0 mod n for some 0 ≤ t < r-1.
306 for t := 0; t < r-1; t++ {
307 if len(vk) == 0 { // vk == 0
308 return true
309 }
310 // Optimization: V(k) = 2 is a fixed point for V(k') = V(k)² - 2,
311 // so if V(k) = 2, we can stop: we will never find a future V(k) == 0.
312 if len(vk) == 1 && vk[0] == 2 { // vk == 2
313 return false
314 }
315 // k' = 2k
316 // V(k') = V(2k) = V(k)² - 2
317 t1 = t1.sqr(stk, vk)
318 t1 = t1.sub(t1, natTwo)
319 t2, vk = t2.div(stk, vk, t1, n)
320 }
321 return false
322 }
323