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