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
5package big
6
7import (
8	"fmt"
9	"strings"
10	"testing"
11	"unicode"
12)
13
14var 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
46var 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
118func cutSpace(r rune) rune {
119	if unicode.IsSpace(r) {
120		return -1
121	}
122	return r
123}
124
125func 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
161func 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
183func 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
190func 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
197func 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) = true, 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