// Copyright 2009 The Go Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.

// This file implements signed multi-precision integers.

package big

import (
	
	
	
	
)

// An Int represents a signed multi-precision integer.
// The zero value for an Int represents the value 0.
//
// Operations always take pointer arguments (*Int) rather
// than Int values, and each unique Int value requires
// its own unique *Int pointer. To "copy" an Int value,
// an existing (or newly allocated) Int must be set to
// a new value using the Int.Set method; shallow copies
// of Ints are not supported and may lead to errors.
type Int struct {
	neg bool // sign
	abs nat  // absolute value of the integer
}

var intOne = &Int{false, natOne}

// Sign returns:
//
//	-1 if x <  0
//	 0 if x == 0
//	+1 if x >  0
//
func ( *Int) () int {
	if len(.abs) == 0 {
		return 0
	}
	if .neg {
		return -1
	}
	return 1
}

// SetInt64 sets z to x and returns z.
func ( *Int) ( int64) *Int {
	 := false
	if  < 0 {
		 = true
		 = -
	}
	.abs = .abs.setUint64(uint64())
	.neg = 
	return 
}

// SetUint64 sets z to x and returns z.
func ( *Int) ( uint64) *Int {
	.abs = .abs.setUint64()
	.neg = false
	return 
}

// NewInt allocates and returns a new Int set to x.
func ( int64) *Int {
	return new(Int).SetInt64()
}

// Set sets z to x and returns z.
func ( *Int) ( *Int) *Int {
	if  !=  {
		.abs = .abs.set(.abs)
		.neg = .neg
	}
	return 
}

// Bits provides raw (unchecked but fast) access to x by returning its
// absolute value as a little-endian Word slice. The result and x share
// the same underlying array.
// Bits is intended to support implementation of missing low-level Int
// functionality outside this package; it should be avoided otherwise.
func ( *Int) () []Word {
	return .abs
}

// SetBits provides raw (unchecked but fast) access to z by setting its
// value to abs, interpreted as a little-endian Word slice, and returning
// z. The result and abs share the same underlying array.
// SetBits is intended to support implementation of missing low-level Int
// functionality outside this package; it should be avoided otherwise.
func ( *Int) ( []Word) *Int {
	.abs = nat().norm()
	.neg = false
	return 
}

// Abs sets z to |x| (the absolute value of x) and returns z.
func ( *Int) ( *Int) *Int {
	.Set()
	.neg = false
	return 
}

// Neg sets z to -x and returns z.
func ( *Int) ( *Int) *Int {
	.Set()
	.neg = len(.abs) > 0 && !.neg // 0 has no sign
	return 
}

// Add sets z to the sum x+y and returns z.
func ( *Int) (,  *Int) *Int {
	 := .neg
	if .neg == .neg {
		// x + y == x + y
		// (-x) + (-y) == -(x + y)
		.abs = .abs.add(.abs, .abs)
	} else {
		// x + (-y) == x - y == -(y - x)
		// (-x) + y == y - x == -(x - y)
		if .abs.cmp(.abs) >= 0 {
			.abs = .abs.sub(.abs, .abs)
		} else {
			 = !
			.abs = .abs.sub(.abs, .abs)
		}
	}
	.neg = len(.abs) > 0 &&  // 0 has no sign
	return 
}

// Sub sets z to the difference x-y and returns z.
func ( *Int) (,  *Int) *Int {
	 := .neg
	if .neg != .neg {
		// x - (-y) == x + y
		// (-x) - y == -(x + y)
		.abs = .abs.add(.abs, .abs)
	} else {
		// x - y == x - y == -(y - x)
		// (-x) - (-y) == y - x == -(x - y)
		if .abs.cmp(.abs) >= 0 {
			.abs = .abs.sub(.abs, .abs)
		} else {
			 = !
			.abs = .abs.sub(.abs, .abs)
		}
	}
	.neg = len(.abs) > 0 &&  // 0 has no sign
	return 
}

// Mul sets z to the product x*y and returns z.
func ( *Int) (,  *Int) *Int {
	// x * y == x * y
	// x * (-y) == -(x * y)
	// (-x) * y == -(x * y)
	// (-x) * (-y) == x * y
	if  ==  {
		.abs = .abs.sqr(.abs)
		.neg = false
		return 
	}
	.abs = .abs.mul(.abs, .abs)
	.neg = len(.abs) > 0 && .neg != .neg // 0 has no sign
	return 
}

// MulRange sets z to the product of all integers
// in the range [a, b] inclusively and returns z.
// If a > b (empty range), the result is 1.
func ( *Int) (,  int64) *Int {
	switch {
	case  > :
		return .SetInt64(1) // empty range
	case  <= 0 &&  >= 0:
		return .SetInt64(0) // range includes 0
	}
	// a <= b && (b < 0 || a > 0)

	 := false
	if  < 0 {
		 = (-)&1 == 0
		,  = -, -
	}

	.abs = .abs.mulRange(uint64(), uint64())
	.neg = 
	return 
}

// Binomial sets z to the binomial coefficient of (n, k) and returns z.
func ( *Int) (,  int64) *Int {
	// reduce the number of multiplications by reducing k
	if /2 <  &&  <=  {
		 =  -  // Binomial(n, k) == Binomial(n, n-k)
	}
	var ,  Int
	.MulRange(-+1, )
	.MulRange(1, )
	return .Quo(&, &)
}

// Quo sets z to the quotient x/y for y != 0 and returns z.
// If y == 0, a division-by-zero run-time panic occurs.
// Quo implements truncated division (like Go); see QuoRem for more details.
func ( *Int) (,  *Int) *Int {
	.abs, _ = .abs.div(nil, .abs, .abs)
	.neg = len(.abs) > 0 && .neg != .neg // 0 has no sign
	return 
}

// Rem sets z to the remainder x%y for y != 0 and returns z.
// If y == 0, a division-by-zero run-time panic occurs.
// Rem implements truncated modulus (like Go); see QuoRem for more details.
func ( *Int) (,  *Int) *Int {
	_, .abs = nat(nil).div(.abs, .abs, .abs)
	.neg = len(.abs) > 0 && .neg // 0 has no sign
	return 
}

// QuoRem sets z to the quotient x/y and r to the remainder x%y
// and returns the pair (z, r) for y != 0.
// If y == 0, a division-by-zero run-time panic occurs.
//
// QuoRem implements T-division and modulus (like Go):
//
//	q = x/y      with the result truncated to zero
//	r = x - y*q
//
// (See Daan Leijen, ``Division and Modulus for Computer Scientists''.)
// See DivMod for Euclidean division and modulus (unlike Go).
//
func ( *Int) (, ,  *Int) (*Int, *Int) {
	.abs, .abs = .abs.div(.abs, .abs, .abs)
	.neg, .neg = len(.abs) > 0 && .neg != .neg, len(.abs) > 0 && .neg // 0 has no sign
	return , 
}

// Div sets z to the quotient x/y for y != 0 and returns z.
// If y == 0, a division-by-zero run-time panic occurs.
// Div implements Euclidean division (unlike Go); see DivMod for more details.
func ( *Int) (,  *Int) *Int {
	 := .neg // z may be an alias for y
	var  Int
	.QuoRem(, , &)
	if .neg {
		if  {
			.Add(, intOne)
		} else {
			.Sub(, intOne)
		}
	}
	return 
}

// Mod sets z to the modulus x%y for y != 0 and returns z.
// If y == 0, a division-by-zero run-time panic occurs.
// Mod implements Euclidean modulus (unlike Go); see DivMod for more details.
func ( *Int) (,  *Int) *Int {
	 :=  // save y
	if  ==  || alias(.abs, .abs) {
		 = new(Int).Set()
	}
	var  Int
	.QuoRem(, , )
	if .neg {
		if .neg {
			.Sub(, )
		} else {
			.Add(, )
		}
	}
	return 
}

// DivMod sets z to the quotient x div y and m to the modulus x mod y
// and returns the pair (z, m) for y != 0.
// If y == 0, a division-by-zero run-time panic occurs.
//
// DivMod implements Euclidean division and modulus (unlike Go):
//
//	q = x div y  such that
//	m = x - y*q  with 0 <= m < |y|
//
// (See Raymond T. Boute, ``The Euclidean definition of the functions
// div and mod''. ACM Transactions on Programming Languages and
// Systems (TOPLAS), 14(2):127-144, New York, NY, USA, 4/1992.
// ACM press.)
// See QuoRem for T-division and modulus (like Go).
//
func ( *Int) (, ,  *Int) (*Int, *Int) {
	 :=  // save y
	if  ==  || alias(.abs, .abs) {
		 = new(Int).Set()
	}
	.QuoRem(, , )
	if .neg {
		if .neg {
			.Add(, intOne)
			.Sub(, )
		} else {
			.Sub(, intOne)
			.Add(, )
		}
	}
	return , 
}

// Cmp compares x and y and returns:
//
//   -1 if x <  y
//    0 if x == y
//   +1 if x >  y
//
func ( *Int) ( *Int) ( int) {
	// x cmp y == x cmp y
	// x cmp (-y) == x
	// (-x) cmp y == y
	// (-x) cmp (-y) == -(x cmp y)
	switch {
	case  == :
		// nothing to do
	case .neg == .neg:
		 = .abs.cmp(.abs)
		if .neg {
			 = -
		}
	case .neg:
		 = -1
	default:
		 = 1
	}
	return
}

// CmpAbs compares the absolute values of x and y and returns:
//
//   -1 if |x| <  |y|
//    0 if |x| == |y|
//   +1 if |x| >  |y|
//
func ( *Int) ( *Int) int {
	return .abs.cmp(.abs)
}

// low32 returns the least significant 32 bits of x.
func low32( nat) uint32 {
	if len() == 0 {
		return 0
	}
	return uint32([0])
}

// low64 returns the least significant 64 bits of x.
func low64( nat) uint64 {
	if len() == 0 {
		return 0
	}
	 := uint64([0])
	if _W == 32 && len() > 1 {
		return uint64([1])<<32 | 
	}
	return 
}

// Int64 returns the int64 representation of x.
// If x cannot be represented in an int64, the result is undefined.
func ( *Int) () int64 {
	 := int64(low64(.abs))
	if .neg {
		 = -
	}
	return 
}

// Uint64 returns the uint64 representation of x.
// If x cannot be represented in a uint64, the result is undefined.
func ( *Int) () uint64 {
	return low64(.abs)
}

// IsInt64 reports whether x can be represented as an int64.
func ( *Int) () bool {
	if len(.abs) <= 64/_W {
		 := int64(low64(.abs))
		return  >= 0 || .neg &&  == -
	}
	return false
}

// IsUint64 reports whether x can be represented as a uint64.
func ( *Int) () bool {
	return !.neg && len(.abs) <= 64/_W
}

// SetString sets z to the value of s, interpreted in the given base,
// and returns z and a boolean indicating success. The entire string
// (not just a prefix) must be valid for success. If SetString fails,
// the value of z is undefined but the returned value is nil.
//
// The base argument must be 0 or a value between 2 and MaxBase.
// For base 0, the number prefix determines the actual base: A prefix of
// ``0b'' or ``0B'' selects base 2, ``0'', ``0o'' or ``0O'' selects base 8,
// and ``0x'' or ``0X'' selects base 16. Otherwise, the selected base is 10
// and no prefix is accepted.
//
// For bases <= 36, lower and upper case letters are considered the same:
// The letters 'a' to 'z' and 'A' to 'Z' represent digit values 10 to 35.
// For bases > 36, the upper case letters 'A' to 'Z' represent the digit
// values 36 to 61.
//
// For base 0, an underscore character ``_'' may appear between a base
// prefix and an adjacent digit, and between successive digits; such
// underscores do not change the value of the number.
// Incorrect placement of underscores is reported as an error if there
// are no other errors. If base != 0, underscores are not recognized
// and act like any other character that is not a valid digit.
//
func ( *Int) ( string,  int) (*Int, bool) {
	return .setFromScanner(strings.NewReader(), )
}

// setFromScanner implements SetString given an io.ByteScanner.
// For documentation see comments of SetString.
func ( *Int) ( io.ByteScanner,  int) (*Int, bool) {
	if , ,  := .scan(, );  != nil {
		return nil, false
	}
	// entire content must have been consumed
	if ,  := .ReadByte();  != io.EOF {
		return nil, false
	}
	return , true // err == io.EOF => scan consumed all content of r
}

// SetBytes interprets buf as the bytes of a big-endian unsigned
// integer, sets z to that value, and returns z.
func ( *Int) ( []byte) *Int {
	.abs = .abs.setBytes()
	.neg = false
	return 
}

// Bytes returns the absolute value of x as a big-endian byte slice.
//
// To use a fixed length slice, or a preallocated one, use FillBytes.
func ( *Int) () []byte {
	 := make([]byte, len(.abs)*_S)
	return [.abs.bytes():]
}

// FillBytes sets buf to the absolute value of x, storing it as a zero-extended
// big-endian byte slice, and returns buf.
//
// If the absolute value of x doesn't fit in buf, FillBytes will panic.
func ( *Int) ( []byte) []byte {
	// Clear whole buffer. (This gets optimized into a memclr.)
	for  := range  {
		[] = 0
	}
	.abs.bytes()
	return 
}

// BitLen returns the length of the absolute value of x in bits.
// The bit length of 0 is 0.
func ( *Int) () int {
	return .abs.bitLen()
}

// TrailingZeroBits returns the number of consecutive least significant zero
// bits of |x|.
func ( *Int) () uint {
	return .abs.trailingZeroBits()
}

// Exp sets z = x**y mod |m| (i.e. the sign of m is ignored), and returns z.
// If m == nil or m == 0, z = x**y unless y <= 0 then z = 1. If m != 0, y < 0,
// and x and m are not relatively prime, z is unchanged and nil is returned.
//
// Modular exponentiation of inputs of a particular size is not a
// cryptographically constant-time operation.
func ( *Int) (, ,  *Int) *Int {
	// See Knuth, volume 2, section 4.6.3.
	 := .abs
	if .neg {
		if  == nil || len(.abs) == 0 {
			return .SetInt64(1)
		}
		// for y < 0: x**y mod m == (x**(-1))**|y| mod m
		 := new(Int).ModInverse(, )
		if  == nil {
			return nil
		}
		 = .abs
	}
	 := .abs

	var  nat
	if  != nil {
		 = .abs // m.abs may be nil for m == 0
	}

	.abs = .abs.expNN(, , )
	.neg = len(.abs) > 0 && .neg && len() > 0 && [0]&1 == 1 // 0 has no sign
	if .neg && len() > 0 {
		// make modulus result positive
		.abs = .abs.sub(, .abs) // z == x**y mod |m| && 0 <= z < |m|
		.neg = false
	}

	return 
}

// GCD sets z to the greatest common divisor of a and b and returns z.
// If x or y are not nil, GCD sets their value such that z = a*x + b*y.
//
// a and b may be positive, zero or negative. (Before Go 1.14 both had
// to be > 0.) Regardless of the signs of a and b, z is always >= 0.
//
// If a == b == 0, GCD sets z = x = y = 0.
//
// If a == 0 and b != 0, GCD sets z = |b|, x = 0, y = sign(b) * 1.
//
// If a != 0 and b == 0, GCD sets z = |a|, x = sign(a) * 1, y = 0.
func ( *Int) (, , ,  *Int) *Int {
	if len(.abs) == 0 || len(.abs) == 0 {
		, , ,  := len(.abs), len(.abs), .neg, .neg
		if  == 0 {
			.Set()
		} else {
			.Set()
		}
		.neg = false
		if  != nil {
			if  == 0 {
				.SetUint64(0)
			} else {
				.SetUint64(1)
				.neg = 
			}
		}
		if  != nil {
			if  == 0 {
				.SetUint64(0)
			} else {
				.SetUint64(1)
				.neg = 
			}
		}
		return 
	}

	return .lehmerGCD(, , , )
}

// lehmerSimulate attempts to simulate several Euclidean update steps
// using the leading digits of A and B.  It returns u0, u1, v0, v1
// such that A and B can be updated as:
//		A = u0*A + v0*B
//		B = u1*A + v1*B
// Requirements: A >= B and len(B.abs) >= 2
// Since we are calculating with full words to avoid overflow,
// we use 'even' to track the sign of the cosequences.
// For even iterations: u0, v1 >= 0 && u1, v0 <= 0
// For odd  iterations: u0, v1 <= 0 && u1, v0 >= 0
func lehmerSimulate(,  *Int) (, , ,  Word,  bool) {
	// initialize the digits
	var , , ,  Word

	 := len(.abs) // m >= 2
	 := len(.abs) // n >= m >= 2

	// extract the top Word of bits from A and B
	 := nlz(.abs[-1])
	 = .abs[-1]<< | .abs[-2]>>(_W-)
	// B may have implicit zero words in the high bits if the lengths differ
	switch {
	case  == :
		 = .abs[-1]<< | .abs[-2]>>(_W-)
	case  == +1:
		 = .abs[-2] >> (_W - )
	default:
		 = 0
	}

	// Since we are calculating with full words to avoid overflow,
	// we use 'even' to track the sign of the cosequences.
	// For even iterations: u0, v1 >= 0 && u1, v0 <= 0
	// For odd  iterations: u0, v1 <= 0 && u1, v0 >= 0
	// The first iteration starts with k=1 (odd).
	 = false
	// variables to track the cosequences
	, ,  = 0, 1, 0
	, ,  = 0, 0, 1

	// Calculate the quotient and cosequences using Collins' stopping condition.
	// Note that overflow of a Word is not possible when computing the remainder
	// sequence and cosequences since the cosequence size is bounded by the input size.
	// See section 4.2 of Jebelean for details.
	for  >=  && - >= + {
		,  := /, %
		,  = , 
		, ,  = , , +*
		, ,  = , , +*
		 = !
	}
	return
}

// lehmerUpdate updates the inputs A and B such that:
//		A = u0*A + v0*B
//		B = u1*A + v1*B
// where the signs of u0, u1, v0, v1 are given by even
// For even == true: u0, v1 >= 0 && u1, v0 <= 0
// For even == false: u0, v1 <= 0 && u1, v0 >= 0
// q, r, s, t are temporary variables to avoid allocations in the multiplication
func lehmerUpdate(, , , , ,  *Int, , , ,  Word,  bool) {

	.abs = .abs.setWord()
	.abs = .abs.setWord()
	.neg = !
	.neg = 

	.Mul(, )
	.Mul(, )

	.abs = .abs.setWord()
	.abs = .abs.setWord()
	.neg = 
	.neg = !

	.Mul(, )
	.Mul(, )

	.Add(, )
	.Add(, )
}

// euclidUpdate performs a single step of the Euclidean GCD algorithm
// if extended is true, it also updates the cosequence Ua, Ub
func euclidUpdate(, , , , , , ,  *Int,  bool) {
	,  = .QuoRem(, , )

	*, *, * = *, *, *

	if  {
		// Ua, Ub = Ub, Ua - q*Ub
		.Set()
		.Mul(, )
		.Sub(, )
		.Set()
	}
}

// lehmerGCD sets z to the greatest common divisor of a and b,
// which both must be != 0, and returns z.
// If x or y are not nil, their values are set such that z = a*x + b*y.
// See Knuth, The Art of Computer Programming, Vol. 2, Section 4.5.2, Algorithm L.
// This implementation uses the improved condition by Collins requiring only one
// quotient and avoiding the possibility of single Word overflow.
// See Jebelean, "Improving the multiprecision Euclidean algorithm",
// Design and Implementation of Symbolic Computation Systems, pp 45-58.
// The cosequences are updated according to Algorithm 10.45 from
// Cohen et al. "Handbook of Elliptic and Hyperelliptic Curve Cryptography" pp 192.
func ( *Int) (, , ,  *Int) *Int {
	var , , ,  *Int

	 = new(Int).Abs()
	 = new(Int).Abs()

	 :=  != nil ||  != nil

	if  {
		// Ua (Ub) tracks how many times input a has been accumulated into A (B).
		 = new(Int).SetInt64(1)
		 = new(Int)
	}

	// temp variables for multiprecision update
	 := new(Int)
	 := new(Int)
	 := new(Int)
	 := new(Int)

	// ensure A >= B
	if .abs.cmp(.abs) < 0 {
		,  = , 
		,  = , 
	}

	// loop invariant A >= B
	for len(.abs) > 1 {
		// Attempt to calculate in single-precision using leading words of A and B.
		, , , ,  := lehmerSimulate(, )

		// multiprecision Step
		if  != 0 {
			// Simulate the effect of the single-precision steps using the cosequences.
			// A = u0*A + v0*B
			// B = u1*A + v1*B
			lehmerUpdate(, , , , , , , , , , )

			if  {
				// Ua = u0*Ua + v0*Ub
				// Ub = u1*Ua + v1*Ub
				lehmerUpdate(, , , , , , , , , , )
			}

		} else {
			// Single-digit calculations failed to simulate any quotients.
			// Do a standard Euclidean step.
			euclidUpdate(, , , , , , , , )
		}
	}

	if len(.abs) > 0 {
		// extended Euclidean algorithm base case if B is a single Word
		if len(.abs) > 1 {
			// A is longer than a single Word, so one update is needed.
			euclidUpdate(, , , , , , , , )
		}
		if len(.abs) > 0 {
			// A and B are both a single Word.
			,  := .abs[0], .abs[0]
			if  {
				var , , ,  Word
				,  = 1, 0
				,  = 0, 1
				 := true
				for  != 0 {
					,  := /, %
					,  = , 
					,  = , +*
					,  = , +*
					 = !
				}

				.abs = .abs.setWord()
				.abs = .abs.setWord()
				.neg = !
				.neg = 

				.Mul(, )
				.Mul(, )

				.Add(, )
			} else {
				for  != 0 {
					,  = , %
				}
			}
			.abs[0] = 
		}
	}
	 := .neg
	if  != nil {
		// avoid aliasing b needed in the division below
		if  ==  {
			.Set()
		} else {
			 = 
		}
		// y = (z - a*x)/b
		.Mul(, ) // y can safely alias a
		if  {
			.neg = !.neg
		}
		.Sub(, )
		.Div(, )
	}

	if  != nil {
		* = *
		if  {
			.neg = !.neg
		}
	}

	* = *

	return 
}

// Rand sets z to a pseudo-random number in [0, n) and returns z.
//
// As this uses the math/rand package, it must not be used for
// security-sensitive work. Use crypto/rand.Int instead.
func ( *Int) ( *rand.Rand,  *Int) *Int {
	.neg = false
	if .neg || len(.abs) == 0 {
		.abs = nil
		return 
	}
	.abs = .abs.random(, .abs, .abs.bitLen())
	return 
}

// ModInverse sets z to the multiplicative inverse of g in the ring ℤ/nℤ
// and returns z. If g and n are not relatively prime, g has no multiplicative
// inverse in the ring ℤ/nℤ.  In this case, z is unchanged and the return value
// is nil.
func ( *Int) (,  *Int) *Int {
	// GCD expects parameters a and b to be > 0.
	if .neg {
		var  Int
		 = .Neg()
	}
	if .neg {
		var  Int
		 = .Mod(, )
	}
	var ,  Int
	.GCD(&, nil, , )

	// if and only if d==1, g and n are relatively prime
	if .Cmp(intOne) != 0 {
		return nil
	}

	// x and y are such that g*x + n*y = 1, therefore x is the inverse element,
	// but it may be negative, so convert to the range 0 <= z < |n|
	if .neg {
		.Add(&, )
	} else {
		.Set(&)
	}
	return 
}

// Jacobi returns the Jacobi symbol (x/y), either +1, -1, or 0.
// The y argument must be an odd integer.
func (,  *Int) int {
	if len(.abs) == 0 || .abs[0]&1 == 0 {
		panic(fmt.Sprintf("big: invalid 2nd argument to Int.Jacobi: need odd integer but got %s", ))
	}

	// We use the formulation described in chapter 2, section 2.4,
	// "The Yacas Book of Algorithms":
	// http://yacas.sourceforge.net/Algo.book.pdf

	var , ,  Int
	.Set()
	.Set()
	 := 1

	if .neg {
		if .neg {
			 = -1
		}
		.neg = false
	}

	for {
		if .Cmp(intOne) == 0 {
			return 
		}
		if len(.abs) == 0 {
			return 0
		}
		.Mod(&, &)
		if len(.abs) == 0 {
			return 0
		}
		// a > 0

		// handle factors of 2 in 'a'
		 := .abs.trailingZeroBits()
		if &1 != 0 {
			 := .abs[0] & 7
			if  == 3 ||  == 5 {
				 = -
			}
		}
		.Rsh(&, ) // a = 2^s*c

		// swap numerator and denominator
		if .abs[0]&3 == 3 && .abs[0]&3 == 3 {
			 = -
		}
		.Set(&)
		.Set(&)
	}
}

// modSqrt3Mod4 uses the identity
//      (a^((p+1)/4))^2  mod p
//   == u^(p+1)          mod p
//   == u^2              mod p
// to calculate the square root of any quadratic residue mod p quickly for 3
// mod 4 primes.
func ( *Int) (,  *Int) *Int {
	 := new(Int).Add(, intOne) // e = p + 1
	.Rsh(, 2)                  // e = (p + 1) / 4
	.Exp(, , )               // z = x^e mod p
	return 
}

// modSqrt5Mod8 uses Atkin's observation that 2 is not a square mod p
//   alpha ==  (2*a)^((p-5)/8)    mod p
//   beta  ==  2*a*alpha^2        mod p  is a square root of -1
//   b     ==  a*alpha*(beta-1)   mod p  is a square root of a
// to calculate the square root of any quadratic residue mod p quickly for 5
// mod 8 primes.
func ( *Int) (,  *Int) *Int {
	// p == 5 mod 8 implies p = e*8 + 5
	// e is the quotient and 5 the remainder on division by 8
	 := new(Int).Rsh(, 3)  // e = (p - 5) / 8
	 := new(Int).Lsh(, 1) // tx = 2*x
	 := new(Int).Exp(, , )
	 := new(Int).Mul(, )
	.Mod(, )
	.Mul(, )
	.Mod(, )
	.Sub(, intOne)
	.Mul(, )
	.Mod(, )
	.Mul(, )
	.Mod(, )
	return 
}

// modSqrtTonelliShanks uses the Tonelli-Shanks algorithm to find the square
// root of a quadratic residue modulo any prime.
func ( *Int) (,  *Int) *Int {
	// Break p-1 into s*2^e such that s is odd.
	var  Int
	.Sub(, intOne)
	 := .abs.trailingZeroBits()
	.Rsh(&, )

	// find some non-square n
	var  Int
	.SetInt64(2)
	for Jacobi(&, ) != -1 {
		.Add(&, intOne)
	}

	// Core of the Tonelli-Shanks algorithm. Follows the description in
	// section 6 of "Square roots from 1; 24, 51, 10 to Dan Shanks" by Ezra
	// Brown:
	// https://www.maa.org/sites/default/files/pdf/upload_library/22/Polya/07468342.di020786.02p0470a.pdf
	var , , ,  Int
	.Add(&, intOne)
	.Rsh(&, 1)
	.Exp(, &, )  // y = x^((s+1)/2)
	.Exp(, &, )  // b = x^s
	.Exp(&, &, ) // g = n^s
	 := 
	for {
		// find the least m such that ord_p(b) = 2^m
		var  uint
		.Set(&)
		for .Cmp(intOne) != 0 {
			.Mul(&, &).Mod(&, )
			++
		}

		if  == 0 {
			return .Set(&)
		}

		.SetInt64(0).SetBit(&, int(--1), 1).Exp(&, &, )
		// t = g^(2^(r-m-1)) mod p
		.Mul(&, &).Mod(&, ) // g = g^(2^(r-m)) mod p
		.Mul(&, &).Mod(&, )
		.Mul(&, &).Mod(&, )
		 = 
	}
}

// ModSqrt sets z to a square root of x mod p if such a square root exists, and
// returns z. The modulus p must be an odd prime. If x is not a square mod p,
// ModSqrt leaves z unchanged and returns nil. This function panics if p is
// not an odd integer.
func ( *Int) (,  *Int) *Int {
	switch Jacobi(, ) {
	case -1:
		return nil // x is not a square mod p
	case 0:
		return .SetInt64(0) // sqrt(0) mod p = 0
	case 1:
		break
	}
	if .neg || .Cmp() >= 0 { // ensure 0 <= x < p
		 = new(Int).Mod(, )
	}

	switch {
	case .abs[0]%4 == 3:
		// Check whether p is 3 mod 4, and if so, use the faster algorithm.
		return .modSqrt3Mod4Prime(, )
	case .abs[0]%8 == 5:
		// Check whether p is 5 mod 8, use Atkin's algorithm.
		return .modSqrt5Mod8Prime(, )
	default:
		// Otherwise, use Tonelli-Shanks.
		return .modSqrtTonelliShanks(, )
	}
}

// Lsh sets z = x << n and returns z.
func ( *Int) ( *Int,  uint) *Int {
	.abs = .abs.shl(.abs, )
	.neg = .neg
	return 
}

// Rsh sets z = x >> n and returns z.
func ( *Int) ( *Int,  uint) *Int {
	if .neg {
		// (-x) >> s == ^(x-1) >> s == ^((x-1) >> s) == -(((x-1) >> s) + 1)
		 := .abs.sub(.abs, natOne) // no underflow because |x| > 0
		 = .shr(, )
		.abs = .add(, natOne)
		.neg = true // z cannot be zero if x is negative
		return 
	}

	.abs = .abs.shr(.abs, )
	.neg = false
	return 
}

// Bit returns the value of the i'th bit of x. That is, it
// returns (x>>i)&1. The bit index i must be >= 0.
func ( *Int) ( int) uint {
	if  == 0 {
		// optimization for common case: odd/even test of x
		if len(.abs) > 0 {
			return uint(.abs[0] & 1) // bit 0 is same for -x
		}
		return 0
	}
	if  < 0 {
		panic("negative bit index")
	}
	if .neg {
		 := nat(nil).sub(.abs, natOne)
		return .bit(uint()) ^ 1
	}

	return .abs.bit(uint())
}

// SetBit sets z to x, with x's i'th bit set to b (0 or 1).
// That is, if b is 1 SetBit sets z = x | (1 << i);
// if b is 0 SetBit sets z = x &^ (1 << i). If b is not 0 or 1,
// SetBit will panic.
func ( *Int) ( *Int,  int,  uint) *Int {
	if  < 0 {
		panic("negative bit index")
	}
	if .neg {
		 := .abs.sub(.abs, natOne)
		 = .setBit(, uint(), ^1)
		.abs = .add(, natOne)
		.neg = len(.abs) > 0
		return 
	}
	.abs = .abs.setBit(.abs, uint(), )
	.neg = false
	return 
}

// And sets z = x & y and returns z.
func ( *Int) (,  *Int) *Int {
	if .neg == .neg {
		if .neg {
			// (-x) & (-y) == ^(x-1) & ^(y-1) == ^((x-1) | (y-1)) == -(((x-1) | (y-1)) + 1)
			 := nat(nil).sub(.abs, natOne)
			 := nat(nil).sub(.abs, natOne)
			.abs = .abs.add(.abs.or(, ), natOne)
			.neg = true // z cannot be zero if x and y are negative
			return 
		}

		// x & y == x & y
		.abs = .abs.and(.abs, .abs)
		.neg = false
		return 
	}

	// x.neg != y.neg
	if .neg {
		,  = ,  // & is symmetric
	}

	// x & (-y) == x & ^(y-1) == x &^ (y-1)
	 := nat(nil).sub(.abs, natOne)
	.abs = .abs.andNot(.abs, )
	.neg = false
	return 
}

// AndNot sets z = x &^ y and returns z.
func ( *Int) (,  *Int) *Int {
	if .neg == .neg {
		if .neg {
			// (-x) &^ (-y) == ^(x-1) &^ ^(y-1) == ^(x-1) & (y-1) == (y-1) &^ (x-1)
			 := nat(nil).sub(.abs, natOne)
			 := nat(nil).sub(.abs, natOne)
			.abs = .abs.andNot(, )
			.neg = false
			return 
		}

		// x &^ y == x &^ y
		.abs = .abs.andNot(.abs, .abs)
		.neg = false
		return 
	}

	if .neg {
		// (-x) &^ y == ^(x-1) &^ y == ^(x-1) & ^y == ^((x-1) | y) == -(((x-1) | y) + 1)
		 := nat(nil).sub(.abs, natOne)
		.abs = .abs.add(.abs.or(, .abs), natOne)
		.neg = true // z cannot be zero if x is negative and y is positive
		return 
	}

	// x &^ (-y) == x &^ ^(y-1) == x & (y-1)
	 := nat(nil).sub(.abs, natOne)
	.abs = .abs.and(.abs, )
	.neg = false
	return 
}

// Or sets z = x | y and returns z.
func ( *Int) (,  *Int) *Int {
	if .neg == .neg {
		if .neg {
			// (-x) | (-y) == ^(x-1) | ^(y-1) == ^((x-1) & (y-1)) == -(((x-1) & (y-1)) + 1)
			 := nat(nil).sub(.abs, natOne)
			 := nat(nil).sub(.abs, natOne)
			.abs = .abs.add(.abs.and(, ), natOne)
			.neg = true // z cannot be zero if x and y are negative
			return 
		}

		// x | y == x | y
		.abs = .abs.or(.abs, .abs)
		.neg = false
		return 
	}

	// x.neg != y.neg
	if .neg {
		,  = ,  // | is symmetric
	}

	// x | (-y) == x | ^(y-1) == ^((y-1) &^ x) == -(^((y-1) &^ x) + 1)
	 := nat(nil).sub(.abs, natOne)
	.abs = .abs.add(.abs.andNot(, .abs), natOne)
	.neg = true // z cannot be zero if one of x or y is negative
	return 
}

// Xor sets z = x ^ y and returns z.
func ( *Int) (,  *Int) *Int {
	if .neg == .neg {
		if .neg {
			// (-x) ^ (-y) == ^(x-1) ^ ^(y-1) == (x-1) ^ (y-1)
			 := nat(nil).sub(.abs, natOne)
			 := nat(nil).sub(.abs, natOne)
			.abs = .abs.xor(, )
			.neg = false
			return 
		}

		// x ^ y == x ^ y
		.abs = .abs.xor(.abs, .abs)
		.neg = false
		return 
	}

	// x.neg != y.neg
	if .neg {
		,  = ,  // ^ is symmetric
	}

	// x ^ (-y) == x ^ ^(y-1) == ^(x ^ (y-1)) == -((x ^ (y-1)) + 1)
	 := nat(nil).sub(.abs, natOne)
	.abs = .abs.add(.abs.xor(.abs, ), natOne)
	.neg = true // z cannot be zero if only one of x or y is negative
	return 
}

// Not sets z = ^x and returns z.
func ( *Int) ( *Int) *Int {
	if .neg {
		// ^(-x) == ^(^(x-1)) == x-1
		.abs = .abs.sub(.abs, natOne)
		.neg = false
		return 
	}

	// ^x == -x-1 == -(x+1)
	.abs = .abs.add(.abs, natOne)
	.neg = true // z cannot be zero if x is positive
	return 
}

// Sqrt sets z to ⌊√x⌋, the largest integer such that z² ≤ x, and returns z.
// It panics if x is negative.
func ( *Int) ( *Int) *Int {
	if .neg {
		panic("square root of negative number")
	}
	.neg = false
	.abs = .abs.sqrt(.abs)
	return 
}