Adding upstream version 1.16.10.upstream/1.16.10upstream

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

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)
+	}
+}