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  	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