Source File
int.go
Belonging Package
math/big
// 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.
//
// Note that methods may leak the Int's value through timing side-channels.
// Because of this and because of the scope and complexity of the
// implementation, Int is not well-suited to implement cryptographic operations.
// The standard library avoids exposing non-trivial Int methods to
// attacker-controlled inputs and the determination of whether a bug in math/big
// is considered a security vulnerability might depend on the impact on the
// standard library.
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 {
// This function is used in cryptographic operations. It must not leak
// anything but the Int's sign and bit size through side-channels. Any
// changes must be reviewed by a security expert.
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 {
// This code is arranged to be inlineable and produce
// zero allocations when inlined. See issue 29951.
:= uint64()
if < 0 {
= -
}
var []Word
if == 0 {
} else if _W == 32 && >>32 != 0 {
= []Word{Word(), Word( >> 32)}
} else {
= []Word{Word()}
}
return &Int{neg: < 0, abs: }
}
// 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 {
// This function is used in cryptographic operations. It must not leak
// anything but the Int's sign and bit size through side-channels. Any
// changes must be reviewed by a security expert.
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 C(n, k) and returns z.
func ( *Int) (, int64) *Int {
if > {
return .SetInt64(0)
}
// reduce the number of multiplications by reducing k
if > - {
= - // C(n, k) == C(n, n-k)
}
// C(n, k) == n * (n-1) * ... * (n-k+1) / k * (k-1) * ... * 1
// == n * (n-1) * ... * (n-k+1) / 1 * (1+1) * ... * k
//
// Using the multiplicative formula produces smaller values
// at each step, requiring fewer allocations and computations:
//
// z = 1
// for i := 0; i < k; i = i+1 {
// z *= n-i
// z /= i+1
// }
//
// finally to avoid computing i+1 twice per loop:
//
// z = 1
// i := 0
// for i < k {
// z *= n-i
// i++
// z /= i
// }
var , , , Int
.SetInt64()
.SetInt64()
.Set(intOne)
for .Cmp(&) < 0 {
.Mul(, .Sub(&, &))
.Add(&, intOne)
.Quo(, &)
}
return
}
// 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 ( nat) uint32 {
if len() == 0 {
return 0
}
return uint32([0])
}
// low64 returns the least significant 64 bits of x.
func ( 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
}
// Float64 returns the float64 value nearest x,
// and an indication of any rounding that occurred.
func ( *Int) () (float64, Accuracy) {
:= .abs.bitLen() // NB: still uses slow crypto impl!
if == 0 {
return 0.0, Exact
}
// Fast path: no more than 53 significant bits.
if <= 53 || < 64 && -int(.abs.trailingZeroBits()) <= 53 {
:= float64(low64(.abs))
if .neg {
= -
}
return , Exact
}
return new(Float).SetInt().Float64()
}
// 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 {
// This function is used in cryptographic operations. It must not leak
// anything but the Int's sign and bit size through side-channels. Any
// changes must be reviewed by a security expert.
:= 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 {
// This function is used in cryptographic operations. It must not leak
// anything but the Int's sign and bit size through side-channels. Any
// changes must be reviewed by a security expert.
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 {
return .exp(, , , false)
}
func ( *Int) (, , *Int) *Int {
return .exp(, , , true)
}
func ( *Int) (, , *Int, bool) *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 {
if == || alias(.abs, .abs) {
= new(Int).Set()
}
= .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 (, *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 (, , , , , *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 (, , , , , , , *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 {
// z.neg is not modified before the if check, because z and n might alias.
if .neg || len(.abs) == 0 {
.neg = false
.abs = nil
return
}
.neg = false
.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. If n == 0, a division-by-zero run-time panic occurs.
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
}
func ( nat) (, nat) nat {
// TODO(rsc): ModInverse should be implemented in terms of this function.
return (&Int{abs: }).ModInverse(&Int{abs: }, &Int{abs: }).abs
}
// 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", .String()))
}
// 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
}
// modSqrt5Mod8Prime 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, its behavior is undefined if p is odd but not prime.
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
}
The pages are generated with Golds v0.6.7. (GOOS=linux GOARCH=amd64) Golds is a Go 101 project developed by Tapir Liu. PR and bug reports are welcome and can be submitted to the issue list. Please follow @Go100and1 (reachable from the left QR code) to get the latest news of Golds. |