prime_test.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 (
     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  	stk := getStack()
   163  	defer stk.free()
   164  
   165  	p, _ := new(Int).SetString("203956878356401977405765866929034577280193993314348263094772646453283062722701277632936616063144088173312372882677123879538709400158306567338328279154499698366071906766440037074217117805690872792848149112022286332144876183376326512083574821647933992961249917319836219304274280243803104015000563790123", 10)
   166  	for _, n := range []int{0, 1, 5, 10, 20} {
   167  		b.Run(fmt.Sprintf("n=%d", n), func(b *testing.B) {
   168  			for i := 0; i < b.N; i++ {
   169  				p.ProbablyPrime(n)
   170  			}
   171  		})
   172  	}
   173  
   174  	b.Run("Lucas", func(b *testing.B) {
   175  		for i := 0; i < b.N; i++ {
   176  			p.abs.probablyPrimeLucas(stk)
   177  		}
   178  	})
   179  	b.Run("MillerRabinBase2", func(b *testing.B) {
   180  		for i := 0; i < b.N; i++ {
   181  			p.abs.probablyPrimeMillerRabin(stk, 1, true)
   182  		}
   183  	})
   184  }
   185  
   186  func TestMillerRabinPseudoprimes(t *testing.T) {
   187  	stk := getStack()
   188  	defer stk.free()
   189  
   190  	testPseudoprimes(t, "probablyPrimeMillerRabin",
   191  		func(n nat) bool { return n.probablyPrimeMillerRabin(stk, 1, true) && !n.probablyPrimeLucas(stk) },
   192  		// https://oeis.org/A001262
   193  		[]int{2047, 3277, 4033, 4681, 8321, 15841, 29341, 42799, 49141, 52633, 65281, 74665, 80581, 85489, 88357, 90751})
   194  }
   195  
   196  func TestLucasPseudoprimes(t *testing.T) {
   197  	stk := getStack()
   198  	defer stk.free()
   199  
   200  	testPseudoprimes(t, "probablyPrimeLucas",
   201  		func(n nat) bool { return n.probablyPrimeLucas(stk) && !n.probablyPrimeMillerRabin(stk, 1, true) },
   202  		// https://oeis.org/A217719
   203  		[]int{989, 3239, 5777, 10877, 27971, 29681, 30739, 31631, 39059, 72389, 73919, 75077})
   204  }
   205  
   206  func testPseudoprimes(t *testing.T, name string, cond func(nat) bool, want []int) {
   207  	n := nat{1}
   208  	for i := 3; i < 100000; i += 2 {
   209  		if testing.Short() {
   210  			if len(want) == 0 {
   211  				break
   212  			}
   213  			if i < want[0]-2 {
   214  				i = want[0] - 2
   215  			}
   216  		}
   217  		n[0] = Word(i)
   218  		pseudo := cond(n)
   219  		if pseudo && (len(want) == 0 || i != want[0]) {
   220  			t.Errorf("%s(%v, base=2) = true, want false", name, i)
   221  		} else if !pseudo && len(want) >= 1 && i == want[0] {
   222  			t.Errorf("%s(%v, base=2) = false, want true", name, i)
   223  		}
   224  		if len(want) > 0 && i == want[0] {
   225  			want = want[1:]
   226  		}
   227  	}
   228  	if len(want) > 0 {
   229  		t.Fatalf("forgot to test %v", want)
   230  	}
   231  }
   232
View as plain text