diff options
Diffstat (limited to 'src/math/big/prime_test.go')
| -rw-r--r-- | src/math/big/prime_test.go | 222 |
1 files changed, 222 insertions, 0 deletions
diff --git a/src/math/big/prime_test.go b/src/math/big/prime_test.go new file mode 100644 index 0000000..8596e33 --- /dev/null +++ b/src/math/big/prime_test.go @@ -0,0 +1,222 @@ +// Copyright 2016 The Go Authors. All rights reserved. +// Use of this source code is governed by a BSD-style +// license that can be found in the LICENSE file. + +package big + +import ( + "fmt" + "strings" + "testing" + "unicode" +) + +var primes = []string{ + "2", + "3", + "5", + "7", + "11", + + "13756265695458089029", + "13496181268022124907", + "10953742525620032441", + "17908251027575790097", + + // https://golang.org/issue/638 + "18699199384836356663", + + "98920366548084643601728869055592650835572950932266967461790948584315647051443", + "94560208308847015747498523884063394671606671904944666360068158221458669711639", + + // https://primes.utm.edu/lists/small/small3.html + "449417999055441493994709297093108513015373787049558499205492347871729927573118262811508386655998299074566974373711472560655026288668094291699357843464363003144674940345912431129144354948751003607115263071543163", + "230975859993204150666423538988557839555560243929065415434980904258310530753006723857139742334640122533598517597674807096648905501653461687601339782814316124971547968912893214002992086353183070342498989426570593", + "5521712099665906221540423207019333379125265462121169655563495403888449493493629943498064604536961775110765377745550377067893607246020694972959780839151452457728855382113555867743022746090187341871655890805971735385789993", + "203956878356401977405765866929034577280193993314348263094772646453283062722701277632936616063144088173312372882677123879538709400158306567338328279154499698366071906766440037074217117805690872792848149112022286332144876183376326512083574821647933992961249917319836219304274280243803104015000563790123", + + // ECC primes: https://tools.ietf.org/html/draft-ladd-safecurves-02 + "3618502788666131106986593281521497120414687020801267626233049500247285301239", // Curve1174: 2^251-9 + "57896044618658097711785492504343953926634992332820282019728792003956564819949", // Curve25519: 2^255-19 + "9850501549098619803069760025035903451269934817616361666987073351061430442874302652853566563721228910201656997576599", // E-382: 2^382-105 + "42307582002575910332922579714097346549017899709713998034217522897561970639123926132812109468141778230245837569601494931472367", // Curve41417: 2^414-17 + "6864797660130609714981900799081393217269435300143305409394463459185543183397656052122559640661454554977296311391480858037121987999716643812574028291115057151", // E-521: 2^521-1 +} + +var composites = []string{ + "0", + "1", + "21284175091214687912771199898307297748211672914763848041968395774954376176754", + "6084766654921918907427900243509372380954290099172559290432744450051395395951", + "84594350493221918389213352992032324280367711247940675652888030554255915464401", + "82793403787388584738507275144194252681", + + // Arnault, "Rabin-Miller Primality Test: Composite Numbers Which Pass It", + // Mathematics of Computation, 64(209) (January 1995), pp. 335-361. + "1195068768795265792518361315725116351898245581", // strong pseudoprime to prime bases 2 through 29 + // strong pseudoprime to all prime bases up to 200 + ` + 80383745745363949125707961434194210813883768828755814583748891752229 + 74273765333652186502336163960045457915042023603208766569966760987284 + 0439654082329287387918508691668573282677617710293896977394701670823 + 0428687109997439976544144845341155872450633409279022275296229414984 + 2306881685404326457534018329786111298960644845216191652872597534901`, + + // Extra-strong Lucas pseudoprimes. https://oeis.org/A217719 + "989", + "3239", + "5777", + "10877", + "27971", + "29681", + "30739", + "31631", + "39059", + "72389", + "73919", + "75077", + "100127", + "113573", + "125249", + "137549", + "137801", + "153931", + "155819", + "161027", + "162133", + "189419", + "218321", + "231703", + "249331", + "370229", + "429479", + "430127", + "459191", + "473891", + "480689", + "600059", + "621781", + "632249", + "635627", + + "3673744903", + "3281593591", + "2385076987", + "2738053141", + "2009621503", + "1502682721", + "255866131", + "117987841", + "587861", + + "6368689", + "8725753", + "80579735209", + "105919633", +} + +func cutSpace(r rune) rune { + if unicode.IsSpace(r) { + return -1 + } + return r +} + +func TestProbablyPrime(t *testing.T) { + nreps := 20 + if testing.Short() { + nreps = 1 + } + for i, s := range primes { + p, _ := new(Int).SetString(s, 10) + if !p.ProbablyPrime(nreps) || nreps != 1 && !p.ProbablyPrime(1) || !p.ProbablyPrime(0) { + t.Errorf("#%d prime found to be non-prime (%s)", i, s) + } + } + + for i, s := range composites { + s = strings.Map(cutSpace, s) + c, _ := new(Int).SetString(s, 10) + if c.ProbablyPrime(nreps) || nreps != 1 && c.ProbablyPrime(1) || c.ProbablyPrime(0) { + t.Errorf("#%d composite found to be prime (%s)", i, s) + } + } + + // check that ProbablyPrime panics if n <= 0 + c := NewInt(11) // a prime + for _, n := range []int{-1, 0, 1} { + func() { + defer func() { + if n < 0 && recover() == nil { + t.Fatalf("expected panic from ProbablyPrime(%d)", n) + } + }() + if !c.ProbablyPrime(n) { + t.Fatalf("%v should be a prime", c) + } + }() + } +} + +func BenchmarkProbablyPrime(b *testing.B) { + p, _ := new(Int).SetString("203956878356401977405765866929034577280193993314348263094772646453283062722701277632936616063144088173312372882677123879538709400158306567338328279154499698366071906766440037074217117805690872792848149112022286332144876183376326512083574821647933992961249917319836219304274280243803104015000563790123", 10) + for _, n := range []int{0, 1, 5, 10, 20} { + b.Run(fmt.Sprintf("n=%d", n), func(b *testing.B) { + for i := 0; i < b.N; i++ { + p.ProbablyPrime(n) + } + }) + } + + b.Run("Lucas", func(b *testing.B) { + for i := 0; i < b.N; i++ { + p.abs.probablyPrimeLucas() + } + }) + b.Run("MillerRabinBase2", func(b *testing.B) { + for i := 0; i < b.N; i++ { + p.abs.probablyPrimeMillerRabin(1, true) + } + }) +} + +func TestMillerRabinPseudoprimes(t *testing.T) { + testPseudoprimes(t, "probablyPrimeMillerRabin", + func(n nat) bool { return n.probablyPrimeMillerRabin(1, true) && !n.probablyPrimeLucas() }, + // https://oeis.org/A001262 + []int{2047, 3277, 4033, 4681, 8321, 15841, 29341, 42799, 49141, 52633, 65281, 74665, 80581, 85489, 88357, 90751}) +} + +func TestLucasPseudoprimes(t *testing.T) { + testPseudoprimes(t, "probablyPrimeLucas", + func(n nat) bool { return n.probablyPrimeLucas() && !n.probablyPrimeMillerRabin(1, true) }, + // https://oeis.org/A217719 + []int{989, 3239, 5777, 10877, 27971, 29681, 30739, 31631, 39059, 72389, 73919, 75077}) +} + +func testPseudoprimes(t *testing.T, name string, cond func(nat) bool, want []int) { + n := nat{1} + for i := 3; i < 100000; i += 2 { + if testing.Short() { + if len(want) == 0 { + break + } + if i < want[0]-2 { + i = want[0] - 2 + } + } + n[0] = Word(i) + pseudo := cond(n) + if pseudo && (len(want) == 0 || i != want[0]) { + t.Errorf("%s(%v, base=2) = true, want false", name, i) + } else if !pseudo && len(want) >= 1 && i == want[0] { + t.Errorf("%s(%v, base=2) = false, want true", name, i) + } + if len(want) > 0 && i == want[0] { + want = want[1:] + } + } + if len(want) > 0 { + t.Fatalf("forgot to test %v", want) + } +} |