prime_test.go

Documentation: math/big

		 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 (
		 8  	"fmt"
		 9  	"strings"
		10  	"testing"
		11  	"unicode"
		12  )
		13  
		14  var primes = []string{
		15  	"2",
		16  	"3",
		17  	"5",
		18  	"7",
		19  	"11",
		20  
		21  	"13756265695458089029",
		22  	"13496181268022124907",
		23  	"10953742525620032441",
		24  	"17908251027575790097",
		25  
		26  	// https://golang.org/issue/638
		27  	"18699199384836356663",
		28  
		29  	"98920366548084643601728869055592650835572950932266967461790948584315647051443",
		30  	"94560208308847015747498523884063394671606671904944666360068158221458669711639",
		31  
		32  	// https://primes.utm.edu/lists/small/small3.html
		33  	"449417999055441493994709297093108513015373787049558499205492347871729927573118262811508386655998299074566974373711472560655026288668094291699357843464363003144674940345912431129144354948751003607115263071543163",
		34  	"230975859993204150666423538988557839555560243929065415434980904258310530753006723857139742334640122533598517597674807096648905501653461687601339782814316124971547968912893214002992086353183070342498989426570593",
		35  	"5521712099665906221540423207019333379125265462121169655563495403888449493493629943498064604536961775110765377745550377067893607246020694972959780839151452457728855382113555867743022746090187341871655890805971735385789993",
		36  	"203956878356401977405765866929034577280193993314348263094772646453283062722701277632936616063144088173312372882677123879538709400158306567338328279154499698366071906766440037074217117805690872792848149112022286332144876183376326512083574821647933992961249917319836219304274280243803104015000563790123",
		37  
		38  	// ECC primes: https://tools.ietf.org/html/draft-ladd-safecurves-02
		39  	"3618502788666131106986593281521497120414687020801267626233049500247285301239",																																									// Curve1174: 2^251-9
		40  	"57896044618658097711785492504343953926634992332820282019728792003956564819949",																																								 // Curve25519: 2^255-19
		41  	"9850501549098619803069760025035903451269934817616361666987073351061430442874302652853566563721228910201656997576599",																					 // E-382: 2^382-105
		42  	"42307582002575910332922579714097346549017899709713998034217522897561970639123926132812109468141778230245837569601494931472367",																 // Curve41417: 2^414-17
		43  	"6864797660130609714981900799081393217269435300143305409394463459185543183397656052122559640661454554977296311391480858037121987999716643812574028291115057151", // E-521: 2^521-1
		44  }
		45  
		46  var composites = []string{
		47  	"0",
		48  	"1",
		49  	"21284175091214687912771199898307297748211672914763848041968395774954376176754",
		50  	"6084766654921918907427900243509372380954290099172559290432744450051395395951",
		51  	"84594350493221918389213352992032324280367711247940675652888030554255915464401",
		52  	"82793403787388584738507275144194252681",
		53  
		54  	// Arnault, "Rabin-Miller Primality Test: Composite Numbers Which Pass It",
		55  	// Mathematics of Computation, 64(209) (January 1995), pp. 335-361.
		56  	"1195068768795265792518361315725116351898245581", // strong pseudoprime to prime bases 2 through 29
		57  	// strong pseudoprime to all prime bases up to 200
		58  	`
		59  		 80383745745363949125707961434194210813883768828755814583748891752229
		60  			74273765333652186502336163960045457915042023603208766569966760987284
		61  			 0439654082329287387918508691668573282677617710293896977394701670823
		62  				0428687109997439976544144845341155872450633409279022275296229414984
		63  				 2306881685404326457534018329786111298960644845216191652872597534901`,
		64  
		65  	// Extra-strong Lucas pseudoprimes. https://oeis.org/A217719
		66  	"989",
		67  	"3239",
		68  	"5777",
		69  	"10877",
		70  	"27971",
		71  	"29681",
		72  	"30739",
		73  	"31631",
		74  	"39059",
		75  	"72389",
		76  	"73919",
		77  	"75077",
		78  	"100127",
		79  	"113573",
		80  	"125249",
		81  	"137549",
		82  	"137801",
		83  	"153931",
		84  	"155819",
		85  	"161027",
		86  	"162133",
		87  	"189419",
		88  	"218321",
		89  	"231703",
		90  	"249331",
		91  	"370229",
		92  	"429479",
		93  	"430127",
		94  	"459191",
		95  	"473891",
		96  	"480689",
		97  	"600059",
		98  	"621781",
		99  	"632249",
	 100  	"635627",
	 101  
	 102  	"3673744903",
	 103  	"3281593591",
	 104  	"2385076987",
	 105  	"2738053141",
	 106  	"2009621503",
	 107  	"1502682721",
	 108  	"255866131",
	 109  	"117987841",
	 110  	"587861",
	 111  
	 112  	"6368689",
	 113  	"8725753",
	 114  	"80579735209",
	 115  	"105919633",
	 116  }
	 117  
	 118  func cutSpace(r rune) rune {
	 119  	if unicode.IsSpace(r) {
	 120  		return -1
	 121  	}
	 122  	return r
	 123  }
	 124  
	 125  func TestProbablyPrime(t *testing.T) {
	 126  	nreps := 20
	 127  	if testing.Short() {
	 128  		nreps = 1
	 129  	}
	 130  	for i, s := range primes {
	 131  		p, _ := new(Int).SetString(s, 10)
	 132  		if !p.ProbablyPrime(nreps) || nreps != 1 && !p.ProbablyPrime(1) || !p.ProbablyPrime(0) {
	 133  			t.Errorf("#%d prime found to be non-prime (%s)", i, s)
	 134  		}
	 135  	}
	 136  
	 137  	for i, s := range composites {
	 138  		s = strings.Map(cutSpace, s)
	 139  		c, _ := new(Int).SetString(s, 10)
	 140  		if c.ProbablyPrime(nreps) || nreps != 1 && c.ProbablyPrime(1) || c.ProbablyPrime(0) {
	 141  			t.Errorf("#%d composite found to be prime (%s)", i, s)
	 142  		}
	 143  	}
	 144  
	 145  	// check that ProbablyPrime panics if n <= 0
	 146  	c := NewInt(11) // a prime
	 147  	for _, n := range []int{-1, 0, 1} {
	 148  		func() {
	 149  			defer func() {
	 150  				if n < 0 && recover() == nil {
	 151  					t.Fatalf("expected panic from ProbablyPrime(%d)", n)
	 152  				}
	 153  			}()
	 154  			if !c.ProbablyPrime(n) {
	 155  				t.Fatalf("%v should be a prime", c)
	 156  			}
	 157  		}()
	 158  	}
	 159  }
	 160  
	 161  func BenchmarkProbablyPrime(b *testing.B) {
	 162  	p, _ := new(Int).SetString("203956878356401977405765866929034577280193993314348263094772646453283062722701277632936616063144088173312372882677123879538709400158306567338328279154499698366071906766440037074217117805690872792848149112022286332144876183376326512083574821647933992961249917319836219304274280243803104015000563790123", 10)
	 163  	for _, n := range []int{0, 1, 5, 10, 20} {
	 164  		b.Run(fmt.Sprintf("n=%d", n), func(b *testing.B) {
	 165  			for i := 0; i < b.N; i++ {
	 166  				p.ProbablyPrime(n)
	 167  			}
	 168  		})
	 169  	}
	 170  
	 171  	b.Run("Lucas", func(b *testing.B) {
	 172  		for i := 0; i < b.N; i++ {
	 173  			p.abs.probablyPrimeLucas()
	 174  		}
	 175  	})
	 176  	b.Run("MillerRabinBase2", func(b *testing.B) {
	 177  		for i := 0; i < b.N; i++ {
	 178  			p.abs.probablyPrimeMillerRabin(1, true)
	 179  		}
	 180  	})
	 181  }
	 182  
	 183  func TestMillerRabinPseudoprimes(t *testing.T) {
	 184  	testPseudoprimes(t, "probablyPrimeMillerRabin",
	 185  		func(n nat) bool { return n.probablyPrimeMillerRabin(1, true) && !n.probablyPrimeLucas() },
	 186  		// https://oeis.org/A001262
	 187  		[]int{2047, 3277, 4033, 4681, 8321, 15841, 29341, 42799, 49141, 52633, 65281, 74665, 80581, 85489, 88357, 90751})
	 188  }
	 189  
	 190  func TestLucasPseudoprimes(t *testing.T) {
	 191  	testPseudoprimes(t, "probablyPrimeLucas",
	 192  		func(n nat) bool { return n.probablyPrimeLucas() && !n.probablyPrimeMillerRabin(1, true) },
	 193  		// https://oeis.org/A217719
	 194  		[]int{989, 3239, 5777, 10877, 27971, 29681, 30739, 31631, 39059, 72389, 73919, 75077})
	 195  }
	 196  
	 197  func testPseudoprimes(t *testing.T, name string, cond func(nat) bool, want []int) {
	 198  	n := nat{1}
	 199  	for i := 3; i < 100000; i += 2 {
	 200  		if testing.Short() {
	 201  			if len(want) == 0 {
	 202  				break
	 203  			}
	 204  			if i < want[0]-2 {
	 205  				i = want[0] - 2
	 206  			}
	 207  		}
	 208  		n[0] = Word(i)
	 209  		pseudo := cond(n)
	 210  		if pseudo && (len(want) == 0 || i != want[0]) {
	 211  			t.Errorf("%s(%v, base=2) = true, want false", name, i)
	 212  		} else if !pseudo && len(want) >= 1 && i == want[0] {
	 213  			t.Errorf("%s(%v, base=2) = false, want true", name, i)
	 214  		}
	 215  		if len(want) > 0 && i == want[0] {
	 216  			want = want[1:]
	 217  		}
	 218  	}
	 219  	if len(want) > 0 {
	 220  		t.Fatalf("forgot to test %v", want)
	 221  	}
	 222  }
	 223
View as plain text