Source file src/math/big/int_test.go

Documentation: math/big

		 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  
		 5  package big
		 6  
		 7  import (
		 8  	"bytes"
		 9  	"encoding/hex"
		10  	"fmt"
		11  	"math/rand"
		12  	"strconv"
		13  	"strings"
		14  	"testing"
		15  	"testing/quick"
		16  )
		17  
		18  func 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  
		26  type funZZ func(z, x, y *Int) *Int
		27  type argZZ struct {
		28  	z, x, y *Int
		29  }
		30  
		31  var 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  
		40  var 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  
		48  func 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  
		59  func 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  
		72  func 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  
		88  func 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  
		99  func 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  
	 117  func 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).
	 131  func 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  
	 160  func 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  
	 172  func TestMul(t *testing.T) {
	 173  	if err := quick.Check(checkMul, nil); err != nil {
	 174  		t.Error(err)
	 175  	}
	 176  }
	 177  
	 178  var 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  
	 203  func 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  
	 221  func 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  
	 253  func 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"
	 261  var 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  
	 274  func 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  
	 331  func 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  
	 339  func 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  
	 367  func 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  
	 382  func TestSetBytes(t *testing.T) {
	 383  	if err := quick.Check(checkSetBytes, nil); err != nil {
	 384  		t.Error(err)
	 385  	}
	 386  }
	 387  
	 388  func 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  
	 398  func TestBytes(t *testing.T) {
	 399  	if err := quick.Check(checkBytes, nil); err != nil {
	 400  		t.Error(err)
	 401  	}
	 402  }
	 403  
	 404  func 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  
	 426  var 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  
	 444  func 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  
	 464  func 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  
	 483  func 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  
	 495  var 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  
	 513  func 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  
	 527  var 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  
	 607  func 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  
	 652  func 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  
	 662  func 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  
	 672  func 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
	 689  func 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  
	 725  func 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  
	 739  func 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  
	 755  var 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  
	 775  func 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  
	 850  func 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  
	 877  type intShiftTest struct {
	 878  	in		string
	 879  	shift uint
	 880  	out	 string
	 881  }
	 882  
	 883  var 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  
	 910  func 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  
	 925  func 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  
	 940  var 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  
	 962  func 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  
	 977  func 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  
	 992  func 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.
	1020  var cmpAbsTests = []string{
	1021  	"0",
	1022  	"1",
	1023  	"2",
	1024  	"10",
	1025  	"10000000",
	1026  	"2783678367462374683678456387645876387564783686583485",
	1027  	"2783678367462374683678456387645876387564783686583486",
	1028  	"32957394867987420967976567076075976570670947609750670956097509670576075067076027578341538",
	1029  }
	1030  
	1031  func 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  
	1076  func 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  
	1090  var 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  
	1110  func 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  
	1142  var 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  
	1160  func 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  
	1193  var 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  
	1237  type bitFun func(z, x, y *Int) *Int
	1238  
	1239  func 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  
	1249  func 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  
	1261  func 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  
	1270  func 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  
	1282  func 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  
	1319  var 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  
	1338  func 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  
	1362  var 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  
	1375  func 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  
	1387  func 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  
	1397  func 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  
	1407  func 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  
	1417  func 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.
	1429  func 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  
	1438  func 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  
	1447  func 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  
	1456  func 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  
	1467  func 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  
	1478  func 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  
	1496  var 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  
	1511  func 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  
	1529  var 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  
	1540  func 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  
	1572  func 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.
	1585  func 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  
	1621  func 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  
	1674  func 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  
	1711  func 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  
	1727  func 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  
	1733  func 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.
	1767  func 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  
	1785  func 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  
	1794  func 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  
	1804  func 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  
	1815  func 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  
	1831  func 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  
	1844  func 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  

View as plain text