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