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