type Int … var intOne … // Sign returns: // - -1 if x < 0; // - 0 if x == 0; // - +1 if x > 0. func (x *Int) Sign() int { … } // SetInt64 sets z to x and returns z. func (z *Int) SetInt64(x int64) *Int { … } // SetUint64 sets z to x and returns z. func (z *Int) SetUint64(x uint64) *Int { … } // NewInt allocates and returns a new [Int] set to x. func NewInt(x int64) *Int { … } // Set sets z to x and returns z. func (z *Int) Set(x *Int) *Int { … } // 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 (x *Int) Bits() []Word { … } // 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 (z *Int) SetBits(abs []Word) *Int { … } // Abs sets z to |x| (the absolute value of x) and returns z. func (z *Int) Abs(x *Int) *Int { … } // Neg sets z to -x and returns z. func (z *Int) Neg(x *Int) *Int { … } // Add sets z to the sum x+y and returns z. func (z *Int) Add(x, y *Int) *Int { … } // Sub sets z to the difference x-y and returns z. func (z *Int) Sub(x, y *Int) *Int { … } // Mul sets z to the product x*y and returns z. func (z *Int) Mul(x, y *Int) *Int { … } // 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 (z *Int) MulRange(a, b int64) *Int { … } // Binomial sets z to the binomial coefficient C(n, k) and returns z. func (z *Int) Binomial(n, k int64) *Int { … } // 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 [Int.QuoRem] for more details. func (z *Int) Quo(x, y *Int) *Int { … } // 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 [Int.QuoRem] for more details. func (z *Int) Rem(x, y *Int) *Int { … } // 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 [Int.DivMod] for Euclidean division and modulus (unlike Go). func (z *Int) QuoRem(x, y, r *Int) (*Int, *Int) { … } // 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 [Int.DivMod] for more details. func (z *Int) Div(x, y *Int) *Int { … } // 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 [Int.DivMod] for more details. func (z *Int) Mod(x, y *Int) *Int { … } // 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 [Int.QuoRem] for T-division and modulus (like Go). func (z *Int) DivMod(x, y, m *Int) (*Int, *Int) { … } // Cmp compares x and y and returns: // - -1 if x < y; // - 0 if x == y; // - +1 if x > y. func (x *Int) Cmp(y *Int) (r int) { … } // CmpAbs compares the absolute values of x and y and returns: // - -1 if |x| < |y|; // - 0 if |x| == |y|; // - +1 if |x| > |y|. func (x *Int) CmpAbs(y *Int) int { … } // low32 returns the least significant 32 bits of x. func low32(x nat) uint32 { … } // low64 returns the least significant 64 bits of x. func low64(x nat) uint64 { … } // Int64 returns the int64 representation of x. // If x cannot be represented in an int64, the result is undefined. func (x *Int) Int64() int64 { … } // Uint64 returns the uint64 representation of x. // If x cannot be represented in a uint64, the result is undefined. func (x *Int) Uint64() uint64 { … } // IsInt64 reports whether x can be represented as an int64. func (x *Int) IsInt64() bool { … } // IsUint64 reports whether x can be represented as a uint64. func (x *Int) IsUint64() bool { … } // Float64 returns the float64 value nearest x, // and an indication of any rounding that occurred. func (x *Int) Float64() (float64, Accuracy) { … } // 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 (z *Int) SetString(s string, base int) (*Int, bool) { … } // setFromScanner implements SetString given an io.ByteScanner. // For documentation see comments of SetString. func (z *Int) setFromScanner(r io.ByteScanner, base int) (*Int, bool) { … } // SetBytes interprets buf as the bytes of a big-endian unsigned // integer, sets z to that value, and returns z. func (z *Int) SetBytes(buf []byte) *Int { … } // Bytes returns the absolute value of x as a big-endian byte slice. // // To use a fixed length slice, or a preallocated one, use [Int.FillBytes]. func (x *Int) Bytes() []byte { … } // 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 (x *Int) FillBytes(buf []byte) []byte { … } // BitLen returns the length of the absolute value of x in bits. // The bit length of 0 is 0. func (x *Int) BitLen() int { … } // TrailingZeroBits returns the number of consecutive least significant zero // bits of |x|. func (x *Int) TrailingZeroBits() uint { … } // 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 (z *Int) Exp(x, y, m *Int) *Int { … } func (z *Int) expSlow(x, y, m *Int) *Int { … } func (z *Int) exp(x, y, m *Int, slow bool) *Int { … } // 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 (z *Int) GCD(x, y, a, b *Int) *Int { … } // 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(A, B *Int) (u0, u1, v0, v1 Word, even bool) { … } // 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(A, B, q, r, s, t *Int, u0, u1, v0, v1 Word, even bool) { … } // euclidUpdate performs a single step of the Euclidean GCD algorithm // if extended is true, it also updates the cosequence Ua, Ub. func euclidUpdate(A, B, Ua, Ub, q, r, s, t *Int, extended bool) { … } // 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 (z *Int) lehmerGCD(x, y, a, b *Int) *Int { … } // 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 (z *Int) Rand(rnd *rand.Rand, n *Int) *Int { … } // 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 (z *Int) ModInverse(g, n *Int) *Int { … } func (z nat) modInverse(g, n nat) nat { … } // Jacobi returns the Jacobi symbol (x/y), either +1, -1, or 0. // The y argument must be an odd integer. func Jacobi(x, y *Int) int { … } // 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 (z *Int) modSqrt3Mod4Prime(x, p *Int) *Int { … } // 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 (z *Int) modSqrt5Mod8Prime(x, p *Int) *Int { … } // modSqrtTonelliShanks uses the Tonelli-Shanks algorithm to find the square // root of a quadratic residue modulo any prime. func (z *Int) modSqrtTonelliShanks(x, p *Int) *Int { … } // 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 (z *Int) ModSqrt(x, p *Int) *Int { … } // Lsh sets z = x << n and returns z. func (z *Int) Lsh(x *Int, n uint) *Int { … } // Rsh sets z = x >> n and returns z. func (z *Int) Rsh(x *Int, n uint) *Int { … } // 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 (x *Int) Bit(i int) 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 (z *Int) SetBit(x *Int, i int, b uint) *Int { … } // And sets z = x & y and returns z. func (z *Int) And(x, y *Int) *Int { … } // AndNot sets z = x &^ y and returns z. func (z *Int) AndNot(x, y *Int) *Int { … } // Or sets z = x | y and returns z. func (z *Int) Or(x, y *Int) *Int { … } // Xor sets z = x ^ y and returns z. func (z *Int) Xor(x, y *Int) *Int { … } // Not sets z = ^x and returns z. func (z *Int) Not(x *Int) *Int { … } // Sqrt sets z to ⌊√x⌋, the largest integer such that z² ≤ x, and returns z. // It panics if x is negative. func (z *Int) Sqrt(x *Int) *Int { … }
Codebase Browser
go