prime.go

     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).shr(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.shr(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.shl(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
View as plain text