Home | History | Annotate | Download | only in 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 	// http://primes.utm.edu/lists/small/small3.html
     33 	"449417999055441493994709297093108513015373787049558499205492347871729927573118262811508386655998299074566974373711472560655026288668094291699357843464363003144674940345912431129144354948751003607115263071543163",
     34 	"230975859993204150666423538988557839555560243929065415434980904258310530753006723857139742334640122533598517597674807096648905501653461687601339782814316124971547968912893214002992086353183070342498989426570593",
     35 	"5521712099665906221540423207019333379125265462121169655563495403888449493493629943498064604536961775110765377745550377067893607246020694972959780839151452457728855382113555867743022746090187341871655890805971735385789993",
     36 	"203956878356401977405765866929034577280193993314348263094772646453283062722701277632936616063144088173312372882677123879538709400158306567338328279154499698366071906766440037074217117805690872792848149112022286332144876183376326512083574821647933992961249917319836219304274280243803104015000563790123",
     37 
     38 	// ECC primes: http://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 = 3
    129 	}
    130 	for i, s := range primes {
    131 		p, _ := new(Int).SetString(s, 10)
    132 		if !p.ProbablyPrime(nreps) || !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) || 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 		n[0] = Word(i)
    201 		pseudo := cond(n)
    202 		if pseudo && (len(want) == 0 || i != want[0]) {
    203 			t.Errorf("%s(%v, base=2) = %v, want false", name, i)
    204 		} else if !pseudo && len(want) >= 1 && i == want[0] {
    205 			t.Errorf("%s(%v, base=2) = false, want true", name, i)
    206 		}
    207 		if len(want) > 0 && i == want[0] {
    208 			want = want[1:]
    209 		}
    210 	}
    211 	if len(want) > 0 {
    212 		t.Fatalf("forgot to test %v", want)
    213 	}
    214 }
    215