1// Copyright 2009 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	"bytes"
9	"encoding/hex"
10	"fmt"
11	"math/rand"
12	"testing"
13	"testing/quick"
14)
15
16func isNormalized(x *Int) bool {
17	if len(x.abs) == 0 {
18		return !x.neg
19	}
20	// len(x.abs) > 0
21	return x.abs[len(x.abs)-1] != 0
22}
23
24type funZZ func(z, x, y *Int) *Int
25type argZZ struct {
26	z, x, y *Int
27}
28
29var sumZZ = []argZZ{
30	{NewInt(0), NewInt(0), NewInt(0)},
31	{NewInt(1), NewInt(1), NewInt(0)},
32	{NewInt(1111111110), NewInt(123456789), NewInt(987654321)},
33	{NewInt(-1), NewInt(-1), NewInt(0)},
34	{NewInt(864197532), NewInt(-123456789), NewInt(987654321)},
35	{NewInt(-1111111110), NewInt(-123456789), NewInt(-987654321)},
36}
37
38var prodZZ = []argZZ{
39	{NewInt(0), NewInt(0), NewInt(0)},
40	{NewInt(0), NewInt(1), NewInt(0)},
41	{NewInt(1), NewInt(1), NewInt(1)},
42	{NewInt(-991 * 991), NewInt(991), NewInt(-991)},
43	// TODO(gri) add larger products
44}
45
46func TestSignZ(t *testing.T) {
47	var zero Int
48	for _, a := range sumZZ {
49		s := a.z.Sign()
50		e := a.z.Cmp(&zero)
51		if s != e {
52			t.Errorf("got %d; want %d for z = %v", s, e, a.z)
53		}
54	}
55}
56
57func TestSetZ(t *testing.T) {
58	for _, a := range sumZZ {
59		var z Int
60		z.Set(a.z)
61		if !isNormalized(&z) {
62			t.Errorf("%v is not normalized", z)
63		}
64		if (&z).Cmp(a.z) != 0 {
65			t.Errorf("got z = %v; want %v", z, a.z)
66		}
67	}
68}
69
70func TestAbsZ(t *testing.T) {
71	var zero Int
72	for _, a := range sumZZ {
73		var z Int
74		z.Abs(a.z)
75		var e Int
76		e.Set(a.z)
77		if e.Cmp(&zero) < 0 {
78			e.Sub(&zero, &e)
79		}
80		if z.Cmp(&e) != 0 {
81			t.Errorf("got z = %v; want %v", z, e)
82		}
83	}
84}
85
86func testFunZZ(t *testing.T, msg string, f funZZ, a argZZ) {
87	var z Int
88	f(&z, a.x, a.y)
89	if !isNormalized(&z) {
90		t.Errorf("%s%v is not normalized", msg, z)
91	}
92	if (&z).Cmp(a.z) != 0 {
93		t.Errorf("%s%+v\n\tgot z = %v; want %v", msg, a, &z, a.z)
94	}
95}
96
97func TestSumZZ(t *testing.T) {
98	AddZZ := func(z, x, y *Int) *Int { return z.Add(x, y) }
99	SubZZ := func(z, x, y *Int) *Int { return z.Sub(x, y) }
100	for _, a := range sumZZ {
101		arg := a
102		testFunZZ(t, "AddZZ", AddZZ, arg)
103
104		arg = argZZ{a.z, a.y, a.x}
105		testFunZZ(t, "AddZZ symmetric", AddZZ, arg)
106
107		arg = argZZ{a.x, a.z, a.y}
108		testFunZZ(t, "SubZZ", SubZZ, arg)
109
110		arg = argZZ{a.y, a.z, a.x}
111		testFunZZ(t, "SubZZ symmetric", SubZZ, arg)
112	}
113}
114
115func TestProdZZ(t *testing.T) {
116	MulZZ := func(z, x, y *Int) *Int { return z.Mul(x, y) }
117	for _, a := range prodZZ {
118		arg := a
119		testFunZZ(t, "MulZZ", MulZZ, arg)
120
121		arg = argZZ{a.z, a.y, a.x}
122		testFunZZ(t, "MulZZ symmetric", MulZZ, arg)
123	}
124}
125
126// mulBytes returns x*y via grade school multiplication. Both inputs
127// and the result are assumed to be in big-endian representation (to
128// match the semantics of Int.Bytes and Int.SetBytes).
129func mulBytes(x, y []byte) []byte {
130	z := make([]byte, len(x)+len(y))
131
132	// multiply
133	k0 := len(z) - 1
134	for j := len(y) - 1; j >= 0; j-- {
135		d := int(y[j])
136		if d != 0 {
137			k := k0
138			carry := 0
139			for i := len(x) - 1; i >= 0; i-- {
140				t := int(z[k]) + int(x[i])*d + carry
141				z[k], carry = byte(t), t>>8
142				k--
143			}
144			z[k] = byte(carry)
145		}
146		k0--
147	}
148
149	// normalize (remove leading 0's)
150	i := 0
151	for i < len(z) && z[i] == 0 {
152		i++
153	}
154
155	return z[i:]
156}
157
158func checkMul(a, b []byte) bool {
159	var x, y, z1 Int
160	x.SetBytes(a)
161	y.SetBytes(b)
162	z1.Mul(&x, &y)
163
164	var z2 Int
165	z2.SetBytes(mulBytes(a, b))
166
167	return z1.Cmp(&z2) == 0
168}
169
170func TestMul(t *testing.T) {
171	if err := quick.Check(checkMul, nil); err != nil {
172		t.Error(err)
173	}
174}
175
176var mulRangesZ = []struct {
177	a, b int64
178	prod string
179}{
180	// entirely positive ranges are covered by mulRangesN
181	{-1, 1, "0"},
182	{-2, -1, "2"},
183	{-3, -2, "6"},
184	{-3, -1, "-6"},
185	{1, 3, "6"},
186	{-10, -10, "-10"},
187	{0, -1, "1"},                      // empty range
188	{-1, -100, "1"},                   // empty range
189	{-1, 1, "0"},                      // range includes 0
190	{-1e9, 0, "0"},                    // range includes 0
191	{-1e9, 1e9, "0"},                  // range includes 0
192	{-10, -1, "3628800"},              // 10!
193	{-20, -2, "-2432902008176640000"}, // -20!
194	{-99, -1,
195		"-933262154439441526816992388562667004907159682643816214685929" +
196			"638952175999932299156089414639761565182862536979208272237582" +
197			"511852109168640000000000000000000000", // -99!
198	},
199}
200
201func TestMulRangeZ(t *testing.T) {
202	var tmp Int
203	// test entirely positive ranges
204	for i, r := range mulRangesN {
205		prod := tmp.MulRange(int64(r.a), int64(r.b)).String()
206		if prod != r.prod {
207			t.Errorf("#%da: got %s; want %s", i, prod, r.prod)
208		}
209	}
210	// test other ranges
211	for i, r := range mulRangesZ {
212		prod := tmp.MulRange(r.a, r.b).String()
213		if prod != r.prod {
214			t.Errorf("#%db: got %s; want %s", i, prod, r.prod)
215		}
216	}
217}
218
219func TestBinomial(t *testing.T) {
220	var z Int
221	for _, test := range []struct {
222		n, k int64
223		want string
224	}{
225		{0, 0, "1"},
226		{0, 1, "0"},
227		{1, 0, "1"},
228		{1, 1, "1"},
229		{1, 10, "0"},
230		{4, 0, "1"},
231		{4, 1, "4"},
232		{4, 2, "6"},
233		{4, 3, "4"},
234		{4, 4, "1"},
235		{10, 1, "10"},
236		{10, 9, "10"},
237		{10, 5, "252"},
238		{11, 5, "462"},
239		{11, 6, "462"},
240		{100, 10, "17310309456440"},
241		{100, 90, "17310309456440"},
242		{1000, 10, "263409560461970212832400"},
243		{1000, 990, "263409560461970212832400"},
244	} {
245		if got := z.Binomial(test.n, test.k).String(); got != test.want {
246			t.Errorf("Binomial(%d, %d) = %s; want %s", test.n, test.k, got, test.want)
247		}
248	}
249}
250
251func BenchmarkBinomial(b *testing.B) {
252	var z Int
253	for i := b.N - 1; i >= 0; i-- {
254		z.Binomial(1000, 990)
255	}
256}
257
258// Examples from the Go Language Spec, section "Arithmetic operators"
259var divisionSignsTests = []struct {
260	x, y int64
261	q, r int64 // T-division
262	d, m int64 // Euclidian division
263}{
264	{5, 3, 1, 2, 1, 2},
265	{-5, 3, -1, -2, -2, 1},
266	{5, -3, -1, 2, -1, 2},
267	{-5, -3, 1, -2, 2, 1},
268	{1, 2, 0, 1, 0, 1},
269	{8, 4, 2, 0, 2, 0},
270}
271
272func TestDivisionSigns(t *testing.T) {
273	for i, test := range divisionSignsTests {
274		x := NewInt(test.x)
275		y := NewInt(test.y)
276		q := NewInt(test.q)
277		r := NewInt(test.r)
278		d := NewInt(test.d)
279		m := NewInt(test.m)
280
281		q1 := new(Int).Quo(x, y)
282		r1 := new(Int).Rem(x, y)
283		if !isNormalized(q1) {
284			t.Errorf("#%d Quo: %v is not normalized", i, *q1)
285		}
286		if !isNormalized(r1) {
287			t.Errorf("#%d Rem: %v is not normalized", i, *r1)
288		}
289		if q1.Cmp(q) != 0 || r1.Cmp(r) != 0 {
290			t.Errorf("#%d QuoRem: got (%s, %s), want (%s, %s)", i, q1, r1, q, r)
291		}
292
293		q2, r2 := new(Int).QuoRem(x, y, new(Int))
294		if !isNormalized(q2) {
295			t.Errorf("#%d Quo: %v is not normalized", i, *q2)
296		}
297		if !isNormalized(r2) {
298			t.Errorf("#%d Rem: %v is not normalized", i, *r2)
299		}
300		if q2.Cmp(q) != 0 || r2.Cmp(r) != 0 {
301			t.Errorf("#%d QuoRem: got (%s, %s), want (%s, %s)", i, q2, r2, q, r)
302		}
303
304		d1 := new(Int).Div(x, y)
305		m1 := new(Int).Mod(x, y)
306		if !isNormalized(d1) {
307			t.Errorf("#%d Div: %v is not normalized", i, *d1)
308		}
309		if !isNormalized(m1) {
310			t.Errorf("#%d Mod: %v is not normalized", i, *m1)
311		}
312		if d1.Cmp(d) != 0 || m1.Cmp(m) != 0 {
313			t.Errorf("#%d DivMod: got (%s, %s), want (%s, %s)", i, d1, m1, d, m)
314		}
315
316		d2, m2 := new(Int).DivMod(x, y, new(Int))
317		if !isNormalized(d2) {
318			t.Errorf("#%d Div: %v is not normalized", i, *d2)
319		}
320		if !isNormalized(m2) {
321			t.Errorf("#%d Mod: %v is not normalized", i, *m2)
322		}
323		if d2.Cmp(d) != 0 || m2.Cmp(m) != 0 {
324			t.Errorf("#%d DivMod: got (%s, %s), want (%s, %s)", i, d2, m2, d, m)
325		}
326	}
327}
328
329func norm(x nat) nat {
330	i := len(x)
331	for i > 0 && x[i-1] == 0 {
332		i--
333	}
334	return x[:i]
335}
336
337func TestBits(t *testing.T) {
338	for _, test := range []nat{
339		nil,
340		{0},
341		{1},
342		{0, 1, 2, 3, 4},
343		{4, 3, 2, 1, 0},
344		{4, 3, 2, 1, 0, 0, 0, 0},
345	} {
346		var z Int
347		z.neg = true
348		got := z.SetBits(test)
349		want := norm(test)
350		if got.abs.cmp(want) != 0 {
351			t.Errorf("SetBits(%v) = %v; want %v", test, got.abs, want)
352		}
353
354		if got.neg {
355			t.Errorf("SetBits(%v): got negative result", test)
356		}
357
358		bits := nat(z.Bits())
359		if bits.cmp(want) != 0 {
360			t.Errorf("%v.Bits() = %v; want %v", z.abs, bits, want)
361		}
362	}
363}
364
365func checkSetBytes(b []byte) bool {
366	hex1 := hex.EncodeToString(new(Int).SetBytes(b).Bytes())
367	hex2 := hex.EncodeToString(b)
368
369	for len(hex1) < len(hex2) {
370		hex1 = "0" + hex1
371	}
372
373	for len(hex1) > len(hex2) {
374		hex2 = "0" + hex2
375	}
376
377	return hex1 == hex2
378}
379
380func TestSetBytes(t *testing.T) {
381	if err := quick.Check(checkSetBytes, nil); err != nil {
382		t.Error(err)
383	}
384}
385
386func checkBytes(b []byte) bool {
387	// trim leading zero bytes since Bytes() won't return them
388	// (was issue 12231)
389	for len(b) > 0 && b[0] == 0 {
390		b = b[1:]
391	}
392	b2 := new(Int).SetBytes(b).Bytes()
393	return bytes.Equal(b, b2)
394}
395
396func TestBytes(t *testing.T) {
397	if err := quick.Check(checkBytes, nil); err != nil {
398		t.Error(err)
399	}
400}
401
402func checkQuo(x, y []byte) bool {
403	u := new(Int).SetBytes(x)
404	v := new(Int).SetBytes(y)
405
406	if len(v.abs) == 0 {
407		return true
408	}
409
410	r := new(Int)
411	q, r := new(Int).QuoRem(u, v, r)
412
413	if r.Cmp(v) >= 0 {
414		return false
415	}
416
417	uprime := new(Int).Set(q)
418	uprime.Mul(uprime, v)
419	uprime.Add(uprime, r)
420
421	return uprime.Cmp(u) == 0
422}
423
424var quoTests = []struct {
425	x, y string
426	q, r string
427}{
428	{
429		"476217953993950760840509444250624797097991362735329973741718102894495832294430498335824897858659711275234906400899559094370964723884706254265559534144986498357",
430		"9353930466774385905609975137998169297361893554149986716853295022578535724979483772383667534691121982974895531435241089241440253066816724367338287092081996",
431		"50911",
432		"1",
433	},
434	{
435		"11510768301994997771168",
436		"1328165573307167369775",
437		"8",
438		"885443715537658812968",
439	},
440}
441
442func TestQuo(t *testing.T) {
443	if err := quick.Check(checkQuo, nil); err != nil {
444		t.Error(err)
445	}
446
447	for i, test := range quoTests {
448		x, _ := new(Int).SetString(test.x, 10)
449		y, _ := new(Int).SetString(test.y, 10)
450		expectedQ, _ := new(Int).SetString(test.q, 10)
451		expectedR, _ := new(Int).SetString(test.r, 10)
452
453		r := new(Int)
454		q, r := new(Int).QuoRem(x, y, r)
455
456		if q.Cmp(expectedQ) != 0 || r.Cmp(expectedR) != 0 {
457			t.Errorf("#%d got (%s, %s) want (%s, %s)", i, q, r, expectedQ, expectedR)
458		}
459	}
460}
461
462func TestQuoStepD6(t *testing.T) {
463	// See Knuth, Volume 2, section 4.3.1, exercise 21. This code exercises
464	// a code path which only triggers 1 in 10^{-19} cases.
465
466	u := &Int{false, nat{0, 0, 1 + 1<<(_W-1), _M ^ (1 << (_W - 1))}}
467	v := &Int{false, nat{5, 2 + 1<<(_W-1), 1 << (_W - 1)}}
468
469	r := new(Int)
470	q, r := new(Int).QuoRem(u, v, r)
471	const expectedQ64 = "18446744073709551613"
472	const expectedR64 = "3138550867693340382088035895064302439801311770021610913807"
473	const expectedQ32 = "4294967293"
474	const expectedR32 = "39614081266355540837921718287"
475	if q.String() != expectedQ64 && q.String() != expectedQ32 ||
476		r.String() != expectedR64 && r.String() != expectedR32 {
477		t.Errorf("got (%s, %s) want (%s, %s) or (%s, %s)", q, r, expectedQ64, expectedR64, expectedQ32, expectedR32)
478	}
479}
480
481var bitLenTests = []struct {
482	in  string
483	out int
484}{
485	{"-1", 1},
486	{"0", 0},
487	{"1", 1},
488	{"2", 2},
489	{"4", 3},
490	{"0xabc", 12},
491	{"0x8000", 16},
492	{"0x80000000", 32},
493	{"0x800000000000", 48},
494	{"0x8000000000000000", 64},
495	{"0x80000000000000000000", 80},
496	{"-0x4000000000000000000000", 87},
497}
498
499func TestBitLen(t *testing.T) {
500	for i, test := range bitLenTests {
501		x, ok := new(Int).SetString(test.in, 0)
502		if !ok {
503			t.Errorf("#%d test input invalid: %s", i, test.in)
504			continue
505		}
506
507		if n := x.BitLen(); n != test.out {
508			t.Errorf("#%d got %d want %d", i, n, test.out)
509		}
510	}
511}
512
513var expTests = []struct {
514	x, y, m string
515	out     string
516}{
517	// y <= 0
518	{"0", "0", "", "1"},
519	{"1", "0", "", "1"},
520	{"-10", "0", "", "1"},
521	{"1234", "-1", "", "1"},
522
523	// m == 1
524	{"0", "0", "1", "0"},
525	{"1", "0", "1", "0"},
526	{"-10", "0", "1", "0"},
527	{"1234", "-1", "1", "0"},
528
529	// misc
530	{"5", "1", "3", "2"},
531	{"5", "-7", "", "1"},
532	{"-5", "-7", "", "1"},
533	{"5", "0", "", "1"},
534	{"-5", "0", "", "1"},
535	{"5", "1", "", "5"},
536	{"-5", "1", "", "-5"},
537	{"-5", "1", "7", "2"},
538	{"-2", "3", "2", "0"},
539	{"5", "2", "", "25"},
540	{"1", "65537", "2", "1"},
541	{"0x8000000000000000", "2", "", "0x40000000000000000000000000000000"},
542	{"0x8000000000000000", "2", "6719", "4944"},
543	{"0x8000000000000000", "3", "6719", "5447"},
544	{"0x8000000000000000", "1000", "6719", "1603"},
545	{"0x8000000000000000", "1000000", "6719", "3199"},
546	{"0x8000000000000000", "-1000000", "6719", "1"},
547
548	{"0xffffffffffffffffffffffffffffffff", "0x12345678123456781234567812345678123456789", "0x01112222333344445555666677778889", "0x36168FA1DB3AAE6C8CE647E137F97A"},
549
550	{
551		"2938462938472983472983659726349017249287491026512746239764525612965293865296239471239874193284792387498274256129746192347",
552		"298472983472983471903246121093472394872319615612417471234712061",
553		"29834729834729834729347290846729561262544958723956495615629569234729836259263598127342374289365912465901365498236492183464",
554		"23537740700184054162508175125554701713153216681790245129157191391322321508055833908509185839069455749219131480588829346291",
555	},
556	// test case for issue 8822
557	{
558		"11001289118363089646017359372117963499250546375269047542777928006103246876688756735760905680604646624353196869572752623285140408755420374049317646428185270079555372763503115646054602867593662923894140940837479507194934267532831694565516466765025434902348314525627418515646588160955862839022051353653052947073136084780742729727874803457643848197499548297570026926927502505634297079527299004267769780768565695459945235586892627059178884998772989397505061206395455591503771677500931269477503508150175717121828518985901959919560700853226255420793148986854391552859459511723547532575574664944815966793196961286234040892865",
559		"0xB08FFB20760FFED58FADA86DFEF71AD72AA0FA763219618FE022C197E54708BB1191C66470250FCE8879487507CEE41381CA4D932F81C2B3F1AB20B539D50DCD",
560		"0xAC6BDB41324A9A9BF166DE5E1389582FAF72B6651987EE07FC3192943DB56050A37329CBB4A099ED8193E0757767A13DD52312AB4B03310DCD7F48A9DA04FD50E8083969EDB767B0CF6095179A163AB3661A05FBD5FAAAE82918A9962F0B93B855F97993EC975EEAA80D740ADBF4FF747359D041D5C33EA71D281E446B14773BCA97B43A23FB801676BD207A436C6481F1D2B9078717461A5B9D32E688F87748544523B524B0D57D5EA77A2775D2ECFA032CFBDBF52FB3786160279004E57AE6AF874E7303CE53299CCC041C7BC308D82A5698F3A8D0C38271AE35F8E9DBFBB694B5C803D89F7AE435DE236D525F54759B65E372FCD68EF20FA7111F9E4AFF73",
561		"21484252197776302499639938883777710321993113097987201050501182909581359357618579566746556372589385361683610524730509041328855066514963385522570894839035884713051640171474186548713546686476761306436434146475140156284389181808675016576845833340494848283681088886584219750554408060556769486628029028720727393293111678826356480455433909233520504112074401376133077150471237549474149190242010469539006449596611576612573955754349042329130631128234637924786466585703488460540228477440853493392086251021228087076124706778899179648655221663765993962724699135217212118535057766739392069738618682722216712319320435674779146070442",
562	},
563	{
564		"-0x1BCE04427D8032319A89E5C4136456671AC620883F2C4139E57F91307C485AD2D6204F4F87A58262652DB5DBBAC72B0613E51B835E7153BEC6068F5C8D696B74DBD18FEC316AEF73985CF0475663208EB46B4F17DD9DA55367B03323E5491A70997B90C059FB34809E6EE55BCFBD5F2F52233BFE62E6AA9E4E26A1D4C2439883D14F2633D55D8AA66A1ACD5595E778AC3A280517F1157989E70C1A437B849F1877B779CC3CDDEDE2DAA6594A6C66D181A00A5F777EE60596D8773998F6E988DEAE4CCA60E4DDCF9590543C89F74F603259FCAD71660D30294FBBE6490300F78A9D63FA660DC9417B8B9DDA28BEB3977B621B988E23D4D954F322C3540541BC649ABD504C50FADFD9F0987D58A2BF689313A285E773FF02899A6EF887D1D4A0D2",
565		"0xB08FFB20760FFED58FADA86DFEF71AD72AA0FA763219618FE022C197E54708BB1191C66470250FCE8879487507CEE41381CA4D932F81C2B3F1AB20B539D50DCD",
566		"0xAC6BDB41324A9A9BF166DE5E1389582FAF72B6651987EE07FC3192943DB56050A37329CBB4A099ED8193E0757767A13DD52312AB4B03310DCD7F48A9DA04FD50E8083969EDB767B0CF6095179A163AB3661A05FBD5FAAAE82918A9962F0B93B855F97993EC975EEAA80D740ADBF4FF747359D041D5C33EA71D281E446B14773BCA97B43A23FB801676BD207A436C6481F1D2B9078717461A5B9D32E688F87748544523B524B0D57D5EA77A2775D2ECFA032CFBDBF52FB3786160279004E57AE6AF874E7303CE53299CCC041C7BC308D82A5698F3A8D0C38271AE35F8E9DBFBB694B5C803D89F7AE435DE236D525F54759B65E372FCD68EF20FA7111F9E4AFF73",
567		"21484252197776302499639938883777710321993113097987201050501182909581359357618579566746556372589385361683610524730509041328855066514963385522570894839035884713051640171474186548713546686476761306436434146475140156284389181808675016576845833340494848283681088886584219750554408060556769486628029028720727393293111678826356480455433909233520504112074401376133077150471237549474149190242010469539006449596611576612573955754349042329130631128234637924786466585703488460540228477440853493392086251021228087076124706778899179648655221663765993962724699135217212118535057766739392069738618682722216712319320435674779146070442",
568	},
569
570	// test cases for issue 13907
571	{"0xffffffff00000001", "0xffffffff00000001", "0xffffffff00000001", "0"},
572	{"0xffffffffffffffff00000001", "0xffffffffffffffff00000001", "0xffffffffffffffff00000001", "0"},
573	{"0xffffffffffffffffffffffff00000001", "0xffffffffffffffffffffffff00000001", "0xffffffffffffffffffffffff00000001", "0"},
574	{"0xffffffffffffffffffffffffffffffff00000001", "0xffffffffffffffffffffffffffffffff00000001", "0xffffffffffffffffffffffffffffffff00000001", "0"},
575}
576
577func TestExp(t *testing.T) {
578	for i, test := range expTests {
579		x, ok1 := new(Int).SetString(test.x, 0)
580		y, ok2 := new(Int).SetString(test.y, 0)
581		out, ok3 := new(Int).SetString(test.out, 0)
582
583		var ok4 bool
584		var m *Int
585
586		if len(test.m) == 0 {
587			m, ok4 = nil, true
588		} else {
589			m, ok4 = new(Int).SetString(test.m, 0)
590		}
591
592		if !ok1 || !ok2 || !ok3 || !ok4 {
593			t.Errorf("#%d: error in input", i)
594			continue
595		}
596
597		z1 := new(Int).Exp(x, y, m)
598		if !isNormalized(z1) {
599			t.Errorf("#%d: %v is not normalized", i, *z1)
600		}
601		if z1.Cmp(out) != 0 {
602			t.Errorf("#%d: got %x want %x", i, z1, out)
603		}
604
605		if m == nil {
606			// The result should be the same as for m == 0;
607			// specifically, there should be no div-zero panic.
608			m = &Int{abs: nat{}} // m != nil && len(m.abs) == 0
609			z2 := new(Int).Exp(x, y, m)
610			if z2.Cmp(z1) != 0 {
611				t.Errorf("#%d: got %x want %x", i, z2, z1)
612			}
613		}
614	}
615}
616
617func checkGcd(aBytes, bBytes []byte) bool {
618	x := new(Int)
619	y := new(Int)
620	a := new(Int).SetBytes(aBytes)
621	b := new(Int).SetBytes(bBytes)
622
623	d := new(Int).GCD(x, y, a, b)
624	x.Mul(x, a)
625	y.Mul(y, b)
626	x.Add(x, y)
627
628	return x.Cmp(d) == 0
629}
630
631var gcdTests = []struct {
632	d, x, y, a, b string
633}{
634	// a <= 0 || b <= 0
635	{"0", "0", "0", "0", "0"},
636	{"0", "0", "0", "0", "7"},
637	{"0", "0", "0", "11", "0"},
638	{"0", "0", "0", "-77", "35"},
639	{"0", "0", "0", "64515", "-24310"},
640	{"0", "0", "0", "-64515", "-24310"},
641
642	{"1", "-9", "47", "120", "23"},
643	{"7", "1", "-2", "77", "35"},
644	{"935", "-3", "8", "64515", "24310"},
645	{"935000000000000000", "-3", "8", "64515000000000000000", "24310000000000000000"},
646	{"1", "-221", "22059940471369027483332068679400581064239780177629666810348940098015901108344", "98920366548084643601728869055592650835572950932266967461790948584315647051443", "991"},
647
648	// test early exit (after one Euclidean iteration) in binaryGCD
649	{"1", "", "", "1", "98920366548084643601728869055592650835572950932266967461790948584315647051443"},
650}
651
652func testGcd(t *testing.T, d, x, y, a, b *Int) {
653	var X *Int
654	if x != nil {
655		X = new(Int)
656	}
657	var Y *Int
658	if y != nil {
659		Y = new(Int)
660	}
661
662	D := new(Int).GCD(X, Y, a, b)
663	if D.Cmp(d) != 0 {
664		t.Errorf("GCD(%s, %s): got d = %s, want %s", a, b, D, d)
665	}
666	if x != nil && X.Cmp(x) != 0 {
667		t.Errorf("GCD(%s, %s): got x = %s, want %s", a, b, X, x)
668	}
669	if y != nil && Y.Cmp(y) != 0 {
670		t.Errorf("GCD(%s, %s): got y = %s, want %s", a, b, Y, y)
671	}
672
673	// binaryGCD requires a > 0 && b > 0
674	if a.Sign() <= 0 || b.Sign() <= 0 {
675		return
676	}
677
678	D.binaryGCD(a, b)
679	if D.Cmp(d) != 0 {
680		t.Errorf("binaryGcd(%s, %s): got d = %s, want %s", a, b, D, d)
681	}
682
683	// check results in presence of aliasing (issue #11284)
684	a2 := new(Int).Set(a)
685	b2 := new(Int).Set(b)
686	a2.binaryGCD(a2, b2) // result is same as 1st argument
687	if a2.Cmp(d) != 0 {
688		t.Errorf("binaryGcd(%s, %s): got d = %s, want %s", a, b, a2, d)
689	}
690
691	a2 = new(Int).Set(a)
692	b2 = new(Int).Set(b)
693	b2.binaryGCD(a2, b2) // result is same as 2nd argument
694	if b2.Cmp(d) != 0 {
695		t.Errorf("binaryGcd(%s, %s): got d = %s, want %s", a, b, b2, d)
696	}
697}
698
699func TestGcd(t *testing.T) {
700	for _, test := range gcdTests {
701		d, _ := new(Int).SetString(test.d, 0)
702		x, _ := new(Int).SetString(test.x, 0)
703		y, _ := new(Int).SetString(test.y, 0)
704		a, _ := new(Int).SetString(test.a, 0)
705		b, _ := new(Int).SetString(test.b, 0)
706
707		testGcd(t, d, nil, nil, a, b)
708		testGcd(t, d, x, nil, a, b)
709		testGcd(t, d, nil, y, a, b)
710		testGcd(t, d, x, y, a, b)
711	}
712
713	if err := quick.Check(checkGcd, nil); err != nil {
714		t.Error(err)
715	}
716}
717
718var primes = []string{
719	"2",
720	"3",
721	"5",
722	"7",
723	"11",
724
725	"13756265695458089029",
726	"13496181268022124907",
727	"10953742525620032441",
728	"17908251027575790097",
729
730	// https://golang.org/issue/638
731	"18699199384836356663",
732
733	"98920366548084643601728869055592650835572950932266967461790948584315647051443",
734	"94560208308847015747498523884063394671606671904944666360068158221458669711639",
735
736	// http://primes.utm.edu/lists/small/small3.html
737	"449417999055441493994709297093108513015373787049558499205492347871729927573118262811508386655998299074566974373711472560655026288668094291699357843464363003144674940345912431129144354948751003607115263071543163",
738	"230975859993204150666423538988557839555560243929065415434980904258310530753006723857139742334640122533598517597674807096648905501653461687601339782814316124971547968912893214002992086353183070342498989426570593",
739	"5521712099665906221540423207019333379125265462121169655563495403888449493493629943498064604536961775110765377745550377067893607246020694972959780839151452457728855382113555867743022746090187341871655890805971735385789993",
740	"203956878356401977405765866929034577280193993314348263094772646453283062722701277632936616063144088173312372882677123879538709400158306567338328279154499698366071906766440037074217117805690872792848149112022286332144876183376326512083574821647933992961249917319836219304274280243803104015000563790123",
741
742	// ECC primes: http://tools.ietf.org/html/draft-ladd-safecurves-02
743	"3618502788666131106986593281521497120414687020801267626233049500247285301239",                                                                                  // Curve1174: 2^251-9
744	"57896044618658097711785492504343953926634992332820282019728792003956564819949",                                                                                 // Curve25519: 2^255-19
745	"9850501549098619803069760025035903451269934817616361666987073351061430442874302652853566563721228910201656997576599",                                           // E-382: 2^382-105
746	"42307582002575910332922579714097346549017899709713998034217522897561970639123926132812109468141778230245837569601494931472367",                                 // Curve41417: 2^414-17
747	"6864797660130609714981900799081393217269435300143305409394463459185543183397656052122559640661454554977296311391480858037121987999716643812574028291115057151", // E-521: 2^521-1
748}
749
750var composites = []string{
751	"0",
752	"1",
753	"21284175091214687912771199898307297748211672914763848041968395774954376176754",
754	"6084766654921918907427900243509372380954290099172559290432744450051395395951",
755	"84594350493221918389213352992032324280367711247940675652888030554255915464401",
756	"82793403787388584738507275144194252681",
757}
758
759func TestProbablyPrime(t *testing.T) {
760	nreps := 20
761	if testing.Short() {
762		nreps = 1
763	}
764	for i, s := range primes {
765		p, _ := new(Int).SetString(s, 10)
766		if !p.ProbablyPrime(nreps) {
767			t.Errorf("#%d prime found to be non-prime (%s)", i, s)
768		}
769	}
770
771	for i, s := range composites {
772		c, _ := new(Int).SetString(s, 10)
773		if c.ProbablyPrime(nreps) {
774			t.Errorf("#%d composite found to be prime (%s)", i, s)
775		}
776		if testing.Short() {
777			break
778		}
779	}
780
781	// check that ProbablyPrime panics if n <= 0
782	c := NewInt(11) // a prime
783	for _, n := range []int{-1, 0, 1} {
784		func() {
785			defer func() {
786				if n <= 0 && recover() == nil {
787					t.Fatalf("expected panic from ProbablyPrime(%d)", n)
788				}
789			}()
790			if !c.ProbablyPrime(n) {
791				t.Fatalf("%v should be a prime", c)
792			}
793		}()
794	}
795}
796
797type intShiftTest struct {
798	in    string
799	shift uint
800	out   string
801}
802
803var rshTests = []intShiftTest{
804	{"0", 0, "0"},
805	{"-0", 0, "0"},
806	{"0", 1, "0"},
807	{"0", 2, "0"},
808	{"1", 0, "1"},
809	{"1", 1, "0"},
810	{"1", 2, "0"},
811	{"2", 0, "2"},
812	{"2", 1, "1"},
813	{"-1", 0, "-1"},
814	{"-1", 1, "-1"},
815	{"-1", 10, "-1"},
816	{"-100", 2, "-25"},
817	{"-100", 3, "-13"},
818	{"-100", 100, "-1"},
819	{"4294967296", 0, "4294967296"},
820	{"4294967296", 1, "2147483648"},
821	{"4294967296", 2, "1073741824"},
822	{"18446744073709551616", 0, "18446744073709551616"},
823	{"18446744073709551616", 1, "9223372036854775808"},
824	{"18446744073709551616", 2, "4611686018427387904"},
825	{"18446744073709551616", 64, "1"},
826	{"340282366920938463463374607431768211456", 64, "18446744073709551616"},
827	{"340282366920938463463374607431768211456", 128, "1"},
828}
829
830func TestRsh(t *testing.T) {
831	for i, test := range rshTests {
832		in, _ := new(Int).SetString(test.in, 10)
833		expected, _ := new(Int).SetString(test.out, 10)
834		out := new(Int).Rsh(in, test.shift)
835
836		if !isNormalized(out) {
837			t.Errorf("#%d: %v is not normalized", i, *out)
838		}
839		if out.Cmp(expected) != 0 {
840			t.Errorf("#%d: got %s want %s", i, out, expected)
841		}
842	}
843}
844
845func TestRshSelf(t *testing.T) {
846	for i, test := range rshTests {
847		z, _ := new(Int).SetString(test.in, 10)
848		expected, _ := new(Int).SetString(test.out, 10)
849		z.Rsh(z, test.shift)
850
851		if !isNormalized(z) {
852			t.Errorf("#%d: %v is not normalized", i, *z)
853		}
854		if z.Cmp(expected) != 0 {
855			t.Errorf("#%d: got %s want %s", i, z, expected)
856		}
857	}
858}
859
860var lshTests = []intShiftTest{
861	{"0", 0, "0"},
862	{"0", 1, "0"},
863	{"0", 2, "0"},
864	{"1", 0, "1"},
865	{"1", 1, "2"},
866	{"1", 2, "4"},
867	{"2", 0, "2"},
868	{"2", 1, "4"},
869	{"2", 2, "8"},
870	{"-87", 1, "-174"},
871	{"4294967296", 0, "4294967296"},
872	{"4294967296", 1, "8589934592"},
873	{"4294967296", 2, "17179869184"},
874	{"18446744073709551616", 0, "18446744073709551616"},
875	{"9223372036854775808", 1, "18446744073709551616"},
876	{"4611686018427387904", 2, "18446744073709551616"},
877	{"1", 64, "18446744073709551616"},
878	{"18446744073709551616", 64, "340282366920938463463374607431768211456"},
879	{"1", 128, "340282366920938463463374607431768211456"},
880}
881
882func TestLsh(t *testing.T) {
883	for i, test := range lshTests {
884		in, _ := new(Int).SetString(test.in, 10)
885		expected, _ := new(Int).SetString(test.out, 10)
886		out := new(Int).Lsh(in, test.shift)
887
888		if !isNormalized(out) {
889			t.Errorf("#%d: %v is not normalized", i, *out)
890		}
891		if out.Cmp(expected) != 0 {
892			t.Errorf("#%d: got %s want %s", i, out, expected)
893		}
894	}
895}
896
897func TestLshSelf(t *testing.T) {
898	for i, test := range lshTests {
899		z, _ := new(Int).SetString(test.in, 10)
900		expected, _ := new(Int).SetString(test.out, 10)
901		z.Lsh(z, test.shift)
902
903		if !isNormalized(z) {
904			t.Errorf("#%d: %v is not normalized", i, *z)
905		}
906		if z.Cmp(expected) != 0 {
907			t.Errorf("#%d: got %s want %s", i, z, expected)
908		}
909	}
910}
911
912func TestLshRsh(t *testing.T) {
913	for i, test := range rshTests {
914		in, _ := new(Int).SetString(test.in, 10)
915		out := new(Int).Lsh(in, test.shift)
916		out = out.Rsh(out, test.shift)
917
918		if !isNormalized(out) {
919			t.Errorf("#%d: %v is not normalized", i, *out)
920		}
921		if in.Cmp(out) != 0 {
922			t.Errorf("#%d: got %s want %s", i, out, in)
923		}
924	}
925	for i, test := range lshTests {
926		in, _ := new(Int).SetString(test.in, 10)
927		out := new(Int).Lsh(in, test.shift)
928		out.Rsh(out, test.shift)
929
930		if !isNormalized(out) {
931			t.Errorf("#%d: %v is not normalized", i, *out)
932		}
933		if in.Cmp(out) != 0 {
934			t.Errorf("#%d: got %s want %s", i, out, in)
935		}
936	}
937}
938
939var int64Tests = []int64{
940	0,
941	1,
942	-1,
943	4294967295,
944	-4294967295,
945	4294967296,
946	-4294967296,
947	9223372036854775807,
948	-9223372036854775807,
949	-9223372036854775808,
950}
951
952func TestInt64(t *testing.T) {
953	for i, testVal := range int64Tests {
954		in := NewInt(testVal)
955		out := in.Int64()
956
957		if out != testVal {
958			t.Errorf("#%d got %d want %d", i, out, testVal)
959		}
960	}
961}
962
963var uint64Tests = []uint64{
964	0,
965	1,
966	4294967295,
967	4294967296,
968	8589934591,
969	8589934592,
970	9223372036854775807,
971	9223372036854775808,
972	18446744073709551615, // 1<<64 - 1
973}
974
975func TestUint64(t *testing.T) {
976	in := new(Int)
977	for i, testVal := range uint64Tests {
978		in.SetUint64(testVal)
979		out := in.Uint64()
980
981		if out != testVal {
982			t.Errorf("#%d got %d want %d", i, out, testVal)
983		}
984
985		str := fmt.Sprint(testVal)
986		strOut := in.String()
987		if strOut != str {
988			t.Errorf("#%d.String got %s want %s", i, strOut, str)
989		}
990	}
991}
992
993var bitwiseTests = []struct {
994	x, y                 string
995	and, or, xor, andNot string
996}{
997	{"0x00", "0x00", "0x00", "0x00", "0x00", "0x00"},
998	{"0x00", "0x01", "0x00", "0x01", "0x01", "0x00"},
999	{"0x01", "0x00", "0x00", "0x01", "0x01", "0x01"},
1000	{"-0x01", "0x00", "0x00", "-0x01", "-0x01", "-0x01"},
1001	{"-0xaf", "-0x50", "-0xf0", "-0x0f", "0xe1", "0x41"},
1002	{"0x00", "-0x01", "0x00", "-0x01", "-0x01", "0x00"},
1003	{"0x01", "0x01", "0x01", "0x01", "0x00", "0x00"},
1004	{"-0x01", "-0x01", "-0x01", "-0x01", "0x00", "0x00"},
1005	{"0x07", "0x08", "0x00", "0x0f", "0x0f", "0x07"},
1006	{"0x05", "0x0f", "0x05", "0x0f", "0x0a", "0x00"},
1007	{"0xff", "-0x0a", "0xf6", "-0x01", "-0xf7", "0x09"},
1008	{"0x013ff6", "0x9a4e", "0x1a46", "0x01bffe", "0x01a5b8", "0x0125b0"},
1009	{"-0x013ff6", "0x9a4e", "0x800a", "-0x0125b2", "-0x01a5bc", "-0x01c000"},
1010	{"-0x013ff6", "-0x9a4e", "-0x01bffe", "-0x1a46", "0x01a5b8", "0x8008"},
1011	{
1012		"0x1000009dc6e3d9822cba04129bcbe3401",
1013		"0xb9bd7d543685789d57cb918e833af352559021483cdb05cc21fd",
1014		"0x1000001186210100001000009048c2001",
1015		"0xb9bd7d543685789d57cb918e8bfeff7fddb2ebe87dfbbdfe35fd",
1016		"0xb9bd7d543685789d57ca918e8ae69d6fcdb2eae87df2b97215fc",
1017		"0x8c40c2d8822caa04120b8321400",
1018	},
1019	{
1020		"0x1000009dc6e3d9822cba04129bcbe3401",
1021		"-0xb9bd7d543685789d57cb918e833af352559021483cdb05cc21fd",
1022		"0x8c40c2d8822caa04120b8321401",
1023		"-0xb9bd7d543685789d57ca918e82229142459020483cd2014001fd",
1024		"-0xb9bd7d543685789d57ca918e8ae69d6fcdb2eae87df2b97215fe",
1025		"0x1000001186210100001000009048c2000",
1026	},
1027	{
1028		"-0x1000009dc6e3d9822cba04129bcbe3401",
1029		"-0xb9bd7d543685789d57cb918e833af352559021483cdb05cc21fd",
1030		"-0xb9bd7d543685789d57cb918e8bfeff7fddb2ebe87dfbbdfe35fd",
1031		"-0x1000001186210100001000009048c2001",
1032		"0xb9bd7d543685789d57ca918e8ae69d6fcdb2eae87df2b97215fc",
1033		"0xb9bd7d543685789d57ca918e82229142459020483cd2014001fc",
1034	},
1035}
1036
1037type bitFun func(z, x, y *Int) *Int
1038
1039func testBitFun(t *testing.T, msg string, f bitFun, x, y *Int, exp string) {
1040	expected := new(Int)
1041	expected.SetString(exp, 0)
1042
1043	out := f(new(Int), x, y)
1044	if out.Cmp(expected) != 0 {
1045		t.Errorf("%s: got %s want %s", msg, out, expected)
1046	}
1047}
1048
1049func testBitFunSelf(t *testing.T, msg string, f bitFun, x, y *Int, exp string) {
1050	self := new(Int)
1051	self.Set(x)
1052	expected := new(Int)
1053	expected.SetString(exp, 0)
1054
1055	self = f(self, self, y)
1056	if self.Cmp(expected) != 0 {
1057		t.Errorf("%s: got %s want %s", msg, self, expected)
1058	}
1059}
1060
1061func altBit(x *Int, i int) uint {
1062	z := new(Int).Rsh(x, uint(i))
1063	z = z.And(z, NewInt(1))
1064	if z.Cmp(new(Int)) != 0 {
1065		return 1
1066	}
1067	return 0
1068}
1069
1070func altSetBit(z *Int, x *Int, i int, b uint) *Int {
1071	one := NewInt(1)
1072	m := one.Lsh(one, uint(i))
1073	switch b {
1074	case 1:
1075		return z.Or(x, m)
1076	case 0:
1077		return z.AndNot(x, m)
1078	}
1079	panic("set bit is not 0 or 1")
1080}
1081
1082func testBitset(t *testing.T, x *Int) {
1083	n := x.BitLen()
1084	z := new(Int).Set(x)
1085	z1 := new(Int).Set(x)
1086	for i := 0; i < n+10; i++ {
1087		old := z.Bit(i)
1088		old1 := altBit(z1, i)
1089		if old != old1 {
1090			t.Errorf("bitset: inconsistent value for Bit(%s, %d), got %v want %v", z1, i, old, old1)
1091		}
1092		z := new(Int).SetBit(z, i, 1)
1093		z1 := altSetBit(new(Int), z1, i, 1)
1094		if z.Bit(i) == 0 {
1095			t.Errorf("bitset: bit %d of %s got 0 want 1", i, x)
1096		}
1097		if z.Cmp(z1) != 0 {
1098			t.Errorf("bitset: inconsistent value after SetBit 1, got %s want %s", z, z1)
1099		}
1100		z.SetBit(z, i, 0)
1101		altSetBit(z1, z1, i, 0)
1102		if z.Bit(i) != 0 {
1103			t.Errorf("bitset: bit %d of %s got 1 want 0", i, x)
1104		}
1105		if z.Cmp(z1) != 0 {
1106			t.Errorf("bitset: inconsistent value after SetBit 0, got %s want %s", z, z1)
1107		}
1108		altSetBit(z1, z1, i, old)
1109		z.SetBit(z, i, old)
1110		if z.Cmp(z1) != 0 {
1111			t.Errorf("bitset: inconsistent value after SetBit old, got %s want %s", z, z1)
1112		}
1113	}
1114	if z.Cmp(x) != 0 {
1115		t.Errorf("bitset: got %s want %s", z, x)
1116	}
1117}
1118
1119var bitsetTests = []struct {
1120	x string
1121	i int
1122	b uint
1123}{
1124	{"0", 0, 0},
1125	{"0", 200, 0},
1126	{"1", 0, 1},
1127	{"1", 1, 0},
1128	{"-1", 0, 1},
1129	{"-1", 200, 1},
1130	{"0x2000000000000000000000000000", 108, 0},
1131	{"0x2000000000000000000000000000", 109, 1},
1132	{"0x2000000000000000000000000000", 110, 0},
1133	{"-0x2000000000000000000000000001", 108, 1},
1134	{"-0x2000000000000000000000000001", 109, 0},
1135	{"-0x2000000000000000000000000001", 110, 1},
1136}
1137
1138func TestBitSet(t *testing.T) {
1139	for _, test := range bitwiseTests {
1140		x := new(Int)
1141		x.SetString(test.x, 0)
1142		testBitset(t, x)
1143		x = new(Int)
1144		x.SetString(test.y, 0)
1145		testBitset(t, x)
1146	}
1147	for i, test := range bitsetTests {
1148		x := new(Int)
1149		x.SetString(test.x, 0)
1150		b := x.Bit(test.i)
1151		if b != test.b {
1152			t.Errorf("#%d got %v want %v", i, b, test.b)
1153		}
1154	}
1155	z := NewInt(1)
1156	z.SetBit(NewInt(0), 2, 1)
1157	if z.Cmp(NewInt(4)) != 0 {
1158		t.Errorf("destination leaked into result; got %s want 4", z)
1159	}
1160}
1161
1162func BenchmarkBitset(b *testing.B) {
1163	z := new(Int)
1164	z.SetBit(z, 512, 1)
1165	b.ResetTimer()
1166	b.StartTimer()
1167	for i := b.N - 1; i >= 0; i-- {
1168		z.SetBit(z, i&512, 1)
1169	}
1170}
1171
1172func BenchmarkBitsetNeg(b *testing.B) {
1173	z := NewInt(-1)
1174	z.SetBit(z, 512, 0)
1175	b.ResetTimer()
1176	b.StartTimer()
1177	for i := b.N - 1; i >= 0; i-- {
1178		z.SetBit(z, i&512, 0)
1179	}
1180}
1181
1182func BenchmarkBitsetOrig(b *testing.B) {
1183	z := new(Int)
1184	altSetBit(z, z, 512, 1)
1185	b.ResetTimer()
1186	b.StartTimer()
1187	for i := b.N - 1; i >= 0; i-- {
1188		altSetBit(z, z, i&512, 1)
1189	}
1190}
1191
1192func BenchmarkBitsetNegOrig(b *testing.B) {
1193	z := NewInt(-1)
1194	altSetBit(z, z, 512, 0)
1195	b.ResetTimer()
1196	b.StartTimer()
1197	for i := b.N - 1; i >= 0; i-- {
1198		altSetBit(z, z, i&512, 0)
1199	}
1200}
1201
1202// tri generates the trinomial 2**(n*2) - 2**n - 1, which is always 3 mod 4 and
1203// 7 mod 8, so that 2 is always a quadratic residue.
1204func tri(n uint) *Int {
1205	x := NewInt(1)
1206	x.Lsh(x, n)
1207	x2 := new(Int).Lsh(x, n)
1208	x2.Sub(x2, x)
1209	x2.Sub(x2, intOne)
1210	return x2
1211}
1212
1213func BenchmarkModSqrt225_Tonelli(b *testing.B) {
1214	p := tri(225)
1215	x := NewInt(2)
1216	for i := 0; i < b.N; i++ {
1217		x.SetUint64(2)
1218		x.modSqrtTonelliShanks(x, p)
1219	}
1220}
1221
1222func BenchmarkModSqrt224_3Mod4(b *testing.B) {
1223	p := tri(225)
1224	x := new(Int).SetUint64(2)
1225	for i := 0; i < b.N; i++ {
1226		x.SetUint64(2)
1227		x.modSqrt3Mod4Prime(x, p)
1228	}
1229}
1230
1231func BenchmarkModSqrt5430_Tonelli(b *testing.B) {
1232	p := tri(5430)
1233	x := new(Int).SetUint64(2)
1234	for i := 0; i < b.N; i++ {
1235		x.SetUint64(2)
1236		x.modSqrtTonelliShanks(x, p)
1237	}
1238}
1239
1240func BenchmarkModSqrt5430_3Mod4(b *testing.B) {
1241	p := tri(5430)
1242	x := new(Int).SetUint64(2)
1243	for i := 0; i < b.N; i++ {
1244		x.SetUint64(2)
1245		x.modSqrt3Mod4Prime(x, p)
1246	}
1247}
1248
1249func TestBitwise(t *testing.T) {
1250	x := new(Int)
1251	y := new(Int)
1252	for _, test := range bitwiseTests {
1253		x.SetString(test.x, 0)
1254		y.SetString(test.y, 0)
1255
1256		testBitFun(t, "and", (*Int).And, x, y, test.and)
1257		testBitFunSelf(t, "and", (*Int).And, x, y, test.and)
1258		testBitFun(t, "andNot", (*Int).AndNot, x, y, test.andNot)
1259		testBitFunSelf(t, "andNot", (*Int).AndNot, x, y, test.andNot)
1260		testBitFun(t, "or", (*Int).Or, x, y, test.or)
1261		testBitFunSelf(t, "or", (*Int).Or, x, y, test.or)
1262		testBitFun(t, "xor", (*Int).Xor, x, y, test.xor)
1263		testBitFunSelf(t, "xor", (*Int).Xor, x, y, test.xor)
1264	}
1265}
1266
1267var notTests = []struct {
1268	in  string
1269	out string
1270}{
1271	{"0", "-1"},
1272	{"1", "-2"},
1273	{"7", "-8"},
1274	{"0", "-1"},
1275	{"-81910", "81909"},
1276	{
1277		"298472983472983471903246121093472394872319615612417471234712061",
1278		"-298472983472983471903246121093472394872319615612417471234712062",
1279	},
1280}
1281
1282func TestNot(t *testing.T) {
1283	in := new(Int)
1284	out := new(Int)
1285	expected := new(Int)
1286	for i, test := range notTests {
1287		in.SetString(test.in, 10)
1288		expected.SetString(test.out, 10)
1289		out = out.Not(in)
1290		if out.Cmp(expected) != 0 {
1291			t.Errorf("#%d: got %s want %s", i, out, expected)
1292		}
1293		out = out.Not(out)
1294		if out.Cmp(in) != 0 {
1295			t.Errorf("#%d: got %s want %s", i, out, in)
1296		}
1297	}
1298}
1299
1300var modInverseTests = []struct {
1301	element string
1302	modulus string
1303}{
1304	{"1234567", "458948883992"},
1305	{"239487239847", "2410312426921032588552076022197566074856950548502459942654116941958108831682612228890093858261341614673227141477904012196503648957050582631942730706805009223062734745341073406696246014589361659774041027169249453200378729434170325843778659198143763193776859869524088940195577346119843545301547043747207749969763750084308926339295559968882457872412993810129130294592999947926365264059284647209730384947211681434464714438488520940127459844288859336526896320919633919"},
1306}
1307
1308func TestModInverse(t *testing.T) {
1309	var element, modulus, gcd, inverse Int
1310	one := NewInt(1)
1311	for i, test := range modInverseTests {
1312		(&element).SetString(test.element, 10)
1313		(&modulus).SetString(test.modulus, 10)
1314		(&inverse).ModInverse(&element, &modulus)
1315		(&inverse).Mul(&inverse, &element)
1316		(&inverse).Mod(&inverse, &modulus)
1317		if (&inverse).Cmp(one) != 0 {
1318			t.Errorf("#%d: failed (e·e^(-1)=%s)", i, &inverse)
1319		}
1320	}
1321	// exhaustive test for small values
1322	for n := 2; n < 100; n++ {
1323		(&modulus).SetInt64(int64(n))
1324		for x := 1; x < n; x++ {
1325			(&element).SetInt64(int64(x))
1326			(&gcd).GCD(nil, nil, &element, &modulus)
1327			if (&gcd).Cmp(one) != 0 {
1328				continue
1329			}
1330			(&inverse).ModInverse(&element, &modulus)
1331			(&inverse).Mul(&inverse, &element)
1332			(&inverse).Mod(&inverse, &modulus)
1333			if (&inverse).Cmp(one) != 0 {
1334				t.Errorf("ModInverse(%d,%d)*%d%%%d=%d, not 1", &element, &modulus, &element, &modulus, &inverse)
1335			}
1336		}
1337	}
1338}
1339
1340// testModSqrt is a helper for TestModSqrt,
1341// which checks that ModSqrt can compute a square-root of elt^2.
1342func testModSqrt(t *testing.T, elt, mod, sq, sqrt *Int) bool {
1343	var sqChk, sqrtChk, sqrtsq Int
1344	sq.Mul(elt, elt)
1345	sq.Mod(sq, mod)
1346	z := sqrt.ModSqrt(sq, mod)
1347	if z != sqrt {
1348		t.Errorf("ModSqrt returned wrong value %s", z)
1349	}
1350
1351	// test ModSqrt arguments outside the range [0,mod)
1352	sqChk.Add(sq, mod)
1353	z = sqrtChk.ModSqrt(&sqChk, mod)
1354	if z != &sqrtChk || z.Cmp(sqrt) != 0 {
1355		t.Errorf("ModSqrt returned inconsistent value %s", z)
1356	}
1357	sqChk.Sub(sq, mod)
1358	z = sqrtChk.ModSqrt(&sqChk, mod)
1359	if z != &sqrtChk || z.Cmp(sqrt) != 0 {
1360		t.Errorf("ModSqrt returned inconsistent value %s", z)
1361	}
1362
1363	// make sure we actually got a square root
1364	if sqrt.Cmp(elt) == 0 {
1365		return true // we found the "desired" square root
1366	}
1367	sqrtsq.Mul(sqrt, sqrt) // make sure we found the "other" one
1368	sqrtsq.Mod(&sqrtsq, mod)
1369	return sq.Cmp(&sqrtsq) == 0
1370}
1371
1372func TestModSqrt(t *testing.T) {
1373	var elt, mod, modx4, sq, sqrt Int
1374	r := rand.New(rand.NewSource(9))
1375	for i, s := range primes[1:] { // skip 2, use only odd primes
1376		mod.SetString(s, 10)
1377		modx4.Lsh(&mod, 2)
1378
1379		// test a few random elements per prime
1380		for x := 1; x < 5; x++ {
1381			elt.Rand(r, &modx4)
1382			elt.Sub(&elt, &mod) // test range [-mod, 3*mod)
1383			if !testModSqrt(t, &elt, &mod, &sq, &sqrt) {
1384				t.Errorf("#%d: failed (sqrt(e) = %s)", i, &sqrt)
1385			}
1386		}
1387
1388		if testing.Short() && i > 2 {
1389			break
1390		}
1391	}
1392
1393	if testing.Short() {
1394		return
1395	}
1396
1397	// exhaustive test for small values
1398	for n := 3; n < 100; n++ {
1399		mod.SetInt64(int64(n))
1400		if !mod.ProbablyPrime(10) {
1401			continue
1402		}
1403		isSquare := make([]bool, n)
1404
1405		// test all the squares
1406		for x := 1; x < n; x++ {
1407			elt.SetInt64(int64(x))
1408			if !testModSqrt(t, &elt, &mod, &sq, &sqrt) {
1409				t.Errorf("#%d: failed (sqrt(%d,%d) = %s)", x, &elt, &mod, &sqrt)
1410			}
1411			isSquare[sq.Uint64()] = true
1412		}
1413
1414		// test all non-squares
1415		for x := 1; x < n; x++ {
1416			sq.SetInt64(int64(x))
1417			z := sqrt.ModSqrt(&sq, &mod)
1418			if !isSquare[x] && z != nil {
1419				t.Errorf("#%d: failed (sqrt(%d,%d) = nil)", x, &sqrt, &mod)
1420			}
1421		}
1422	}
1423}
1424
1425func TestJacobi(t *testing.T) {
1426	testCases := []struct {
1427		x, y   int64
1428		result int
1429	}{
1430		{0, 1, 1},
1431		{0, -1, 1},
1432		{1, 1, 1},
1433		{1, -1, 1},
1434		{0, 5, 0},
1435		{1, 5, 1},
1436		{2, 5, -1},
1437		{-2, 5, -1},
1438		{2, -5, -1},
1439		{-2, -5, 1},
1440		{3, 5, -1},
1441		{5, 5, 0},
1442		{-5, 5, 0},
1443		{6, 5, 1},
1444		{6, -5, 1},
1445		{-6, 5, 1},
1446		{-6, -5, -1},
1447	}
1448
1449	var x, y Int
1450
1451	for i, test := range testCases {
1452		x.SetInt64(test.x)
1453		y.SetInt64(test.y)
1454		expected := test.result
1455		actual := Jacobi(&x, &y)
1456		if actual != expected {
1457			t.Errorf("#%d: Jacobi(%d, %d) = %d, but expected %d", i, test.x, test.y, actual, expected)
1458		}
1459	}
1460}
1461
1462func TestJacobiPanic(t *testing.T) {
1463	const failureMsg = "test failure"
1464	defer func() {
1465		msg := recover()
1466		if msg == nil || msg == failureMsg {
1467			panic(msg)
1468		}
1469		t.Log(msg)
1470	}()
1471	x := NewInt(1)
1472	y := NewInt(2)
1473	// Jacobi should panic when the second argument is even.
1474	Jacobi(x, y)
1475	panic(failureMsg)
1476}
1477
1478func TestIssue2607(t *testing.T) {
1479	// This code sequence used to hang.
1480	n := NewInt(10)
1481	n.Rand(rand.New(rand.NewSource(9)), n)
1482}
1483