int.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  // This file implements signed multi-precision integers.
     6  
     7  package big
     8  
     9  import (
    10  	"fmt"
    11  	"io"
    12  	"math/rand"
    13  	"strings"
    14  )
    15  
    16  // An Int represents a signed multi-precision integer.
    17  // The zero value for an Int represents the value 0.
    18  type Int struct {
    19  	neg bool // sign
    20  	abs nat  // absolute value of the integer
    21  }
    22  
    23  var intOne = &Int{false, natOne}
    24  
    25  // Sign returns:
    26  //
    27  //	-1 if x <  0
    28  //	 0 if x == 0
    29  //	+1 if x >  0
    30  //
    31  func (x *Int) Sign() int {
    32  	if len(x.abs) == 0 {
    33  		return 0
    34  	}
    35  	if x.neg {
    36  		return -1
    37  	}
    38  	return 1
    39  }
    40  
    41  // SetInt64 sets z to x and returns z.
    42  func (z *Int) SetInt64(x int64) *Int {
    43  	neg := false
    44  	if x < 0 {
    45  		neg = true
    46  		x = -x
    47  	}
    48  	z.abs = z.abs.setUint64(uint64(x))
    49  	z.neg = neg
    50  	return z
    51  }
    52  
    53  // SetUint64 sets z to x and returns z.
    54  func (z *Int) SetUint64(x uint64) *Int {
    55  	z.abs = z.abs.setUint64(x)
    56  	z.neg = false
    57  	return z
    58  }
    59  
    60  // NewInt allocates and returns a new Int set to x.
    61  func NewInt(x int64) *Int {
    62  	return new(Int).SetInt64(x)
    63  }
    64  
    65  // Set sets z to x and returns z.
    66  func (z *Int) Set(x *Int) *Int {
    67  	if z != x {
    68  		z.abs = z.abs.set(x.abs)
    69  		z.neg = x.neg
    70  	}
    71  	return z
    72  }
    73  
    74  // Bits provides raw (unchecked but fast) access to x by returning its
    75  // absolute value as a little-endian Word slice. The result and x share
    76  // the same underlying array.
    77  // Bits is intended to support implementation of missing low-level Int
    78  // functionality outside this package; it should be avoided otherwise.
    79  func (x *Int) Bits() []Word {
    80  	return x.abs
    81  }
    82  
    83  // SetBits provides raw (unchecked but fast) access to z by setting its
    84  // value to abs, interpreted as a little-endian Word slice, and returning
    85  // z. The result and abs share the same underlying array.
    86  // SetBits is intended to support implementation of missing low-level Int
    87  // functionality outside this package; it should be avoided otherwise.
    88  func (z *Int) SetBits(abs []Word) *Int {
    89  	z.abs = nat(abs).norm()
    90  	z.neg = false
    91  	return z
    92  }
    93  
    94  // Abs sets z to |x| (the absolute value of x) and returns z.
    95  func (z *Int) Abs(x *Int) *Int {
    96  	z.Set(x)
    97  	z.neg = false
    98  	return z
    99  }
   100  
   101  // Neg sets z to -x and returns z.
   102  func (z *Int) Neg(x *Int) *Int {
   103  	z.Set(x)
   104  	z.neg = len(z.abs) > 0 && !z.neg // 0 has no sign
   105  	return z
   106  }
   107  
   108  // Add sets z to the sum x+y and returns z.
   109  func (z *Int) Add(x, y *Int) *Int {
   110  	neg := x.neg
   111  	if x.neg == y.neg {
   112  		// x + y == x + y
   113  		// (-x) + (-y) == -(x + y)
   114  		z.abs = z.abs.add(x.abs, y.abs)
   115  	} else {
   116  		// x + (-y) == x - y == -(y - x)
   117  		// (-x) + y == y - x == -(x - y)
   118  		if x.abs.cmp(y.abs) >= 0 {
   119  			z.abs = z.abs.sub(x.abs, y.abs)
   120  		} else {
   121  			neg = !neg
   122  			z.abs = z.abs.sub(y.abs, x.abs)
   123  		}
   124  	}
   125  	z.neg = len(z.abs) > 0 && neg // 0 has no sign
   126  	return z
   127  }
   128  
   129  // Sub sets z to the difference x-y and returns z.
   130  func (z *Int) Sub(x, y *Int) *Int {
   131  	neg := x.neg
   132  	if x.neg != y.neg {
   133  		// x - (-y) == x + y
   134  		// (-x) - y == -(x + y)
   135  		z.abs = z.abs.add(x.abs, y.abs)
   136  	} else {
   137  		// x - y == x - y == -(y - x)
   138  		// (-x) - (-y) == y - x == -(x - y)
   139  		if x.abs.cmp(y.abs) >= 0 {
   140  			z.abs = z.abs.sub(x.abs, y.abs)
   141  		} else {
   142  			neg = !neg
   143  			z.abs = z.abs.sub(y.abs, x.abs)
   144  		}
   145  	}
   146  	z.neg = len(z.abs) > 0 && neg // 0 has no sign
   147  	return z
   148  }
   149  
   150  // Mul sets z to the product x*y and returns z.
   151  func (z *Int) Mul(x, y *Int) *Int {
   152  	// x * y == x * y
   153  	// x * (-y) == -(x * y)
   154  	// (-x) * y == -(x * y)
   155  	// (-x) * (-y) == x * y
   156  	if x == y {
   157  		z.abs = z.abs.sqr(x.abs)
   158  		z.neg = false
   159  		return z
   160  	}
   161  	z.abs = z.abs.mul(x.abs, y.abs)
   162  	z.neg = len(z.abs) > 0 && x.neg != y.neg // 0 has no sign
   163  	return z
   164  }
   165  
   166  // MulRange sets z to the product of all integers
   167  // in the range [a, b] inclusively and returns z.
   168  // If a > b (empty range), the result is 1.
   169  func (z *Int) MulRange(a, b int64) *Int {
   170  	switch {
   171  	case a > b:
   172  		return z.SetInt64(1) // empty range
   173  	case a <= 0 && b >= 0:
   174  		return z.SetInt64(0) // range includes 0
   175  	}
   176  	// a <= b && (b < 0 || a > 0)
   177  
   178  	neg := false
   179  	if a < 0 {
   180  		neg = (b-a)&1 == 0
   181  		a, b = -b, -a
   182  	}
   183  
   184  	z.abs = z.abs.mulRange(uint64(a), uint64(b))
   185  	z.neg = neg
   186  	return z
   187  }
   188  
   189  // Binomial sets z to the binomial coefficient of (n, k) and returns z.
   190  func (z *Int) Binomial(n, k int64) *Int {
   191  	// reduce the number of multiplications by reducing k
   192  	if n/2 < k && k <= n {
   193  		k = n - k // Binomial(n, k) == Binomial(n, n-k)
   194  	}
   195  	var a, b Int
   196  	a.MulRange(n-k+1, n)
   197  	b.MulRange(1, k)
   198  	return z.Quo(&a, &b)
   199  }
   200  
   201  // Quo sets z to the quotient x/y for y != 0 and returns z.
   202  // If y == 0, a division-by-zero run-time panic occurs.
   203  // Quo implements truncated division (like Go); see QuoRem for more details.
   204  func (z *Int) Quo(x, y *Int) *Int {
   205  	z.abs, _ = z.abs.div(nil, x.abs, y.abs)
   206  	z.neg = len(z.abs) > 0 && x.neg != y.neg // 0 has no sign
   207  	return z
   208  }
   209  
   210  // Rem sets z to the remainder x%y for y != 0 and returns z.
   211  // If y == 0, a division-by-zero run-time panic occurs.
   212  // Rem implements truncated modulus (like Go); see QuoRem for more details.
   213  func (z *Int) Rem(x, y *Int) *Int {
   214  	_, z.abs = nat(nil).div(z.abs, x.abs, y.abs)
   215  	z.neg = len(z.abs) > 0 && x.neg // 0 has no sign
   216  	return z
   217  }
   218  
   219  // QuoRem sets z to the quotient x/y and r to the remainder x%y
   220  // and returns the pair (z, r) for y != 0.
   221  // If y == 0, a division-by-zero run-time panic occurs.
   222  //
   223  // QuoRem implements T-division and modulus (like Go):
   224  //
   225  //	q = x/y      with the result truncated to zero
   226  //	r = x - y*q
   227  //
   228  // (See Daan Leijen, ``Division and Modulus for Computer Scientists''.)
   229  // See DivMod for Euclidean division and modulus (unlike Go).
   230  //
   231  func (z *Int) QuoRem(x, y, r *Int) (*Int, *Int) {
   232  	z.abs, r.abs = z.abs.div(r.abs, x.abs, y.abs)
   233  	z.neg, r.neg = len(z.abs) > 0 && x.neg != y.neg, len(r.abs) > 0 && x.neg // 0 has no sign
   234  	return z, r
   235  }
   236  
   237  // Div sets z to the quotient x/y for y != 0 and returns z.
   238  // If y == 0, a division-by-zero run-time panic occurs.
   239  // Div implements Euclidean division (unlike Go); see DivMod for more details.
   240  func (z *Int) Div(x, y *Int) *Int {
   241  	y_neg := y.neg // z may be an alias for y
   242  	var r Int
   243  	z.QuoRem(x, y, &r)
   244  	if r.neg {
   245  		if y_neg {
   246  			z.Add(z, intOne)
   247  		} else {
   248  			z.Sub(z, intOne)
   249  		}
   250  	}
   251  	return z
   252  }
   253  
   254  // Mod sets z to the modulus x%y for y != 0 and returns z.
   255  // If y == 0, a division-by-zero run-time panic occurs.
   256  // Mod implements Euclidean modulus (unlike Go); see DivMod for more details.
   257  func (z *Int) Mod(x, y *Int) *Int {
   258  	y0 := y // save y
   259  	if z == y || alias(z.abs, y.abs) {
   260  		y0 = new(Int).Set(y)
   261  	}
   262  	var q Int
   263  	q.QuoRem(x, y, z)
   264  	if z.neg {
   265  		if y0.neg {
   266  			z.Sub(z, y0)
   267  		} else {
   268  			z.Add(z, y0)
   269  		}
   270  	}
   271  	return z
   272  }
   273  
   274  // DivMod sets z to the quotient x div y and m to the modulus x mod y
   275  // and returns the pair (z, m) for y != 0.
   276  // If y == 0, a division-by-zero run-time panic occurs.
   277  //
   278  // DivMod implements Euclidean division and modulus (unlike Go):
   279  //
   280  //	q = x div y  such that
   281  //	m = x - y*q  with 0 <= m < |y|
   282  //
   283  // (See Raymond T. Boute, ``The Euclidean definition of the functions
   284  // div and mod''. ACM Transactions on Programming Languages and
   285  // Systems (TOPLAS), 14(2):127-144, New York, NY, USA, 4/1992.
   286  // ACM press.)
   287  // See QuoRem for T-division and modulus (like Go).
   288  //
   289  func (z *Int) DivMod(x, y, m *Int) (*Int, *Int) {
   290  	y0 := y // save y
   291  	if z == y || alias(z.abs, y.abs) {
   292  		y0 = new(Int).Set(y)
   293  	}
   294  	z.QuoRem(x, y, m)
   295  	if m.neg {
   296  		if y0.neg {
   297  			z.Add(z, intOne)
   298  			m.Sub(m, y0)
   299  		} else {
   300  			z.Sub(z, intOne)
   301  			m.Add(m, y0)
   302  		}
   303  	}
   304  	return z, m
   305  }
   306  
   307  // Cmp compares x and y and returns:
   308  //
   309  //   -1 if x <  y
   310  //    0 if x == y
   311  //   +1 if x >  y
   312  //
   313  func (x *Int) Cmp(y *Int) (r int) {
   314  	// x cmp y == x cmp y
   315  	// x cmp (-y) == x
   316  	// (-x) cmp y == y
   317  	// (-x) cmp (-y) == -(x cmp y)
   318  	switch {
   319  	case x.neg == y.neg:
   320  		r = x.abs.cmp(y.abs)
   321  		if x.neg {
   322  			r = -r
   323  		}
   324  	case x.neg:
   325  		r = -1
   326  	default:
   327  		r = 1
   328  	}
   329  	return
   330  }
   331  
   332  // CmpAbs compares the absolute values of x and y and returns:
   333  //
   334  //   -1 if |x| <  |y|
   335  //    0 if |x| == |y|
   336  //   +1 if |x| >  |y|
   337  //
   338  func (x *Int) CmpAbs(y *Int) int {
   339  	return x.abs.cmp(y.abs)
   340  }
   341  
   342  // low32 returns the least significant 32 bits of x.
   343  func low32(x nat) uint32 {
   344  	if len(x) == 0 {
   345  		return 0
   346  	}
   347  	return uint32(x[0])
   348  }
   349  
   350  // low64 returns the least significant 64 bits of x.
   351  func low64(x nat) uint64 {
   352  	if len(x) == 0 {
   353  		return 0
   354  	}
   355  	v := uint64(x[0])
   356  	if _W == 32 && len(x) > 1 {
   357  		return uint64(x[1])<<32 | v
   358  	}
   359  	return v
   360  }
   361  
   362  // Int64 returns the int64 representation of x.
   363  // If x cannot be represented in an int64, the result is undefined.
   364  func (x *Int) Int64() int64 {
   365  	v := int64(low64(x.abs))
   366  	if x.neg {
   367  		v = -v
   368  	}
   369  	return v
   370  }
   371  
   372  // Uint64 returns the uint64 representation of x.
   373  // If x cannot be represented in a uint64, the result is undefined.
   374  func (x *Int) Uint64() uint64 {
   375  	return low64(x.abs)
   376  }
   377  
   378  // IsInt64 reports whether x can be represented as an int64.
   379  func (x *Int) IsInt64() bool {
   380  	if len(x.abs) <= 64/_W {
   381  		w := int64(low64(x.abs))
   382  		return w >= 0 || x.neg && w == -w
   383  	}
   384  	return false
   385  }
   386  
   387  // IsUint64 reports whether x can be represented as a uint64.
   388  func (x *Int) IsUint64() bool {
   389  	return !x.neg && len(x.abs) <= 64/_W
   390  }
   391  
   392  // SetString sets z to the value of s, interpreted in the given base,
   393  // and returns z and a boolean indicating success. The entire string
   394  // (not just a prefix) must be valid for success. If SetString fails,
   395  // the value of z is undefined but the returned value is nil.
   396  //
   397  // The base argument must be 0 or a value between 2 and MaxBase. If the base
   398  // is 0, the string prefix determines the actual conversion base. A prefix of
   399  // ``0x'' or ``0X'' selects base 16; the ``0'' prefix selects base 8, and a
   400  // ``0b'' or ``0B'' prefix selects base 2. Otherwise the selected base is 10.
   401  //
   402  // For bases <= 36, lower and upper case letters are considered the same:
   403  // The letters 'a' to 'z' and 'A' to 'Z' represent digit values 10 to 35.
   404  // For bases > 36, the upper case letters 'A' to 'Z' represent the digit
   405  // values 36 to 61.
   406  //
   407  func (z *Int) SetString(s string, base int) (*Int, bool) {
   408  	return z.setFromScanner(strings.NewReader(s), base)
   409  }
   410  
   411  // setFromScanner implements SetString given an io.BytesScanner.
   412  // For documentation see comments of SetString.
   413  func (z *Int) setFromScanner(r io.ByteScanner, base int) (*Int, bool) {
   414  	if _, _, err := z.scan(r, base); err != nil {
   415  		return nil, false
   416  	}
   417  	// entire content must have been consumed
   418  	if _, err := r.ReadByte(); err != io.EOF {
   419  		return nil, false
   420  	}
   421  	return z, true // err == io.EOF => scan consumed all content of r
   422  }
   423  
   424  // SetBytes interprets buf as the bytes of a big-endian unsigned
   425  // integer, sets z to that value, and returns z.
   426  func (z *Int) SetBytes(buf []byte) *Int {
   427  	z.abs = z.abs.setBytes(buf)
   428  	z.neg = false
   429  	return z
   430  }
   431  
   432  // Bytes returns the absolute value of x as a big-endian byte slice.
   433  func (x *Int) Bytes() []byte {
   434  	buf := make([]byte, len(x.abs)*_S)
   435  	return buf[x.abs.bytes(buf):]
   436  }
   437  
   438  // BitLen returns the length of the absolute value of x in bits.
   439  // The bit length of 0 is 0.
   440  func (x *Int) BitLen() int {
   441  	return x.abs.bitLen()
   442  }
   443  
   444  // Exp sets z = x**y mod |m| (i.e. the sign of m is ignored), and returns z.
   445  // If y <= 0, the result is 1 mod |m|; if m == nil or m == 0, z = x**y.
   446  //
   447  // Modular exponentation of inputs of a particular size is not a
   448  // cryptographically constant-time operation.
   449  func (z *Int) Exp(x, y, m *Int) *Int {
   450  	// See Knuth, volume 2, section 4.6.3.
   451  	var yWords nat
   452  	if !y.neg {
   453  		yWords = y.abs
   454  	}
   455  	// y >= 0
   456  
   457  	var mWords nat
   458  	if m != nil {
   459  		mWords = m.abs // m.abs may be nil for m == 0
   460  	}
   461  
   462  	z.abs = z.abs.expNN(x.abs, yWords, mWords)
   463  	z.neg = len(z.abs) > 0 && x.neg && len(yWords) > 0 && yWords[0]&1 == 1 // 0 has no sign
   464  	if z.neg && len(mWords) > 0 {
   465  		// make modulus result positive
   466  		z.abs = z.abs.sub(mWords, z.abs) // z == x**y mod |m| && 0 <= z < |m|
   467  		z.neg = false
   468  	}
   469  
   470  	return z
   471  }
   472  
   473  // GCD sets z to the greatest common divisor of a and b, which both must
   474  // be > 0, and returns z.
   475  // If x or y are not nil, GCD sets their value such that z = a*x + b*y.
   476  // If either a or b is <= 0, GCD sets z = x = y = 0.
   477  func (z *Int) GCD(x, y, a, b *Int) *Int {
   478  	if a.Sign() <= 0 || b.Sign() <= 0 {
   479  		z.SetInt64(0)
   480  		if x != nil {
   481  			x.SetInt64(0)
   482  		}
   483  		if y != nil {
   484  			y.SetInt64(0)
   485  		}
   486  		return z
   487  	}
   488  	if x == nil && y == nil {
   489  		return z.lehmerGCD(a, b)
   490  	}
   491  
   492  	A := new(Int).Set(a)
   493  	B := new(Int).Set(b)
   494  
   495  	X := new(Int)
   496  	lastX := new(Int).SetInt64(1)
   497  
   498  	q := new(Int)
   499  	temp := new(Int)
   500  
   501  	r := new(Int)
   502  	for len(B.abs) > 0 {
   503  		q, r = q.QuoRem(A, B, r)
   504  
   505  		A, B, r = B, r, A
   506  
   507  		temp.Set(X)
   508  		X.Mul(X, q)
   509  		X.Sub(lastX, X)
   510  		lastX.Set(temp)
   511  	}
   512  
   513  	if x != nil {
   514  		*x = *lastX
   515  	}
   516  
   517  	if y != nil {
   518  		// y = (z - a*x)/b
   519  		y.Mul(a, lastX)
   520  		y.Sub(A, y)
   521  		y.Div(y, b)
   522  	}
   523  
   524  	*z = *A
   525  	return z
   526  }
   527  
   528  // lehmerGCD sets z to the greatest common divisor of a and b,
   529  // which both must be > 0, and returns z.
   530  // See Knuth, The Art of Computer Programming, Vol. 2, Section 4.5.2, Algorithm L.
   531  // This implementation uses the improved condition by Collins requiring only one
   532  // quotient and avoiding the possibility of single Word overflow.
   533  // See Jebelean, "Improving the multiprecision Euclidean algorithm",
   534  // Design and Implementation of Symbolic Computation Systems, pp 45-58.
   535  func (z *Int) lehmerGCD(a, b *Int) *Int {
   536  	// ensure a >= b
   537  	if a.abs.cmp(b.abs) < 0 {
   538  		a, b = b, a
   539  	}
   540  
   541  	// don't destroy incoming values of a and b
   542  	B := new(Int).Set(b) // must be set first in case b is an alias of z
   543  	A := z.Set(a)
   544  
   545  	// temp variables for multiprecision update
   546  	t := new(Int)
   547  	r := new(Int)
   548  	s := new(Int)
   549  	w := new(Int)
   550  
   551  	// loop invariant A >= B
   552  	for len(B.abs) > 1 {
   553  		// initialize the digits
   554  		var a1, a2, u0, u1, u2, v0, v1, v2 Word
   555  
   556  		m := len(B.abs) // m >= 2
   557  		n := len(A.abs) // n >= m >= 2
   558  
   559  		// extract the top Word of bits from A and B
   560  		h := nlz(A.abs[n-1])
   561  		a1 = (A.abs[n-1] << h) | (A.abs[n-2] >> (_W - h))
   562  		// B may have implicit zero words in the high bits if the lengths differ
   563  		switch {
   564  		case n == m:
   565  			a2 = (B.abs[n-1] << h) | (B.abs[n-2] >> (_W - h))
   566  		case n == m+1:
   567  			a2 = (B.abs[n-2] >> (_W - h))
   568  		default:
   569  			a2 = 0
   570  		}
   571  
   572  		// Since we are calculating with full words to avoid overflow,
   573  		// we use 'even' to track the sign of the cosequences.
   574  		// For even iterations: u0, v1 >= 0 && u1, v0 <= 0
   575  		// For odd  iterations: u0, v1 <= 0 && u1, v0 >= 0
   576  		// The first iteration starts with k=1 (odd).
   577  		even := false
   578  		// variables to track the cosequences
   579  		u0, u1, u2 = 0, 1, 0
   580  		v0, v1, v2 = 0, 0, 1
   581  
   582  		// Calculate the quotient and cosequences using Collins' stopping condition.
   583  		// Note that overflow of a Word is not possible when computing the remainder
   584  		// sequence and cosequences since the cosequence size is bounded by the input size.
   585  		// See section 4.2 of Jebelean for details.
   586  		for a2 >= v2 && a1-a2 >= v1+v2 {
   587  			q := a1 / a2
   588  			a1, a2 = a2, a1-q*a2
   589  			u0, u1, u2 = u1, u2, u1+q*u2
   590  			v0, v1, v2 = v1, v2, v1+q*v2
   591  			even = !even
   592  		}
   593  
   594  		// multiprecision step
   595  		if v0 != 0 {
   596  			// simulate the effect of the single precision steps using the cosequences
   597  			// A = u0*A + v0*B
   598  			// B = u1*A + v1*B
   599  
   600  			t.abs = t.abs.setWord(u0)
   601  			s.abs = s.abs.setWord(v0)
   602  			t.neg = !even
   603  			s.neg = even
   604  
   605  			t.Mul(A, t)
   606  			s.Mul(B, s)
   607  
   608  			r.abs = r.abs.setWord(u1)
   609  			w.abs = w.abs.setWord(v1)
   610  			r.neg = even
   611  			w.neg = !even
   612  
   613  			r.Mul(A, r)
   614  			w.Mul(B, w)
   615  
   616  			A.Add(t, s)
   617  			B.Add(r, w)
   618  
   619  		} else {
   620  			// single-digit calculations failed to simluate any quotients
   621  			// do a standard Euclidean step
   622  			t.Rem(A, B)
   623  			A, B, t = B, t, A
   624  		}
   625  	}
   626  
   627  	if len(B.abs) > 0 {
   628  		// standard Euclidean algorithm base case for B a single Word
   629  		if len(A.abs) > 1 {
   630  			// A is longer than a single Word
   631  			t.Rem(A, B)
   632  			A, B, t = B, t, A
   633  		}
   634  		if len(B.abs) > 0 {
   635  			// A and B are both a single Word
   636  			a1, a2 := A.abs[0], B.abs[0]
   637  			for a2 != 0 {
   638  				a1, a2 = a2, a1%a2
   639  			}
   640  			A.abs[0] = a1
   641  		}
   642  	}
   643  	*z = *A
   644  	return z
   645  }
   646  
   647  // Rand sets z to a pseudo-random number in [0, n) and returns z.
   648  //
   649  // As this uses the math/rand package, it must not be used for
   650  // security-sensitive work. Use crypto/rand.Int instead.
   651  func (z *Int) Rand(rnd *rand.Rand, n *Int) *Int {
   652  	z.neg = false
   653  	if n.neg || len(n.abs) == 0 {
   654  		z.abs = nil
   655  		return z
   656  	}
   657  	z.abs = z.abs.random(rnd, n.abs, n.abs.bitLen())
   658  	return z
   659  }
   660  
   661  // ModInverse sets z to the multiplicative inverse of g in the ring ℤ/nℤ
   662  // and returns z. If g and n are not relatively prime, the result is undefined.
   663  func (z *Int) ModInverse(g, n *Int) *Int {
   664  	if g.neg {
   665  		// GCD expects parameters a and b to be > 0.
   666  		var g2 Int
   667  		g = g2.Mod(g, n)
   668  	}
   669  	var d Int
   670  	d.GCD(z, nil, g, n)
   671  	// x and y are such that g*x + n*y = d. Since g and n are
   672  	// relatively prime, d = 1. Taking that modulo n results in
   673  	// g*x = 1, therefore x is the inverse element.
   674  	if z.neg {
   675  		z.Add(z, n)
   676  	}
   677  	return z
   678  }
   679  
   680  // Jacobi returns the Jacobi symbol (x/y), either +1, -1, or 0.
   681  // The y argument must be an odd integer.
   682  func Jacobi(x, y *Int) int {
   683  	if len(y.abs) == 0 || y.abs[0]&1 == 0 {
   684  		panic(fmt.Sprintf("big: invalid 2nd argument to Int.Jacobi: need odd integer but got %s", y))
   685  	}
   686  
   687  	// We use the formulation described in chapter 2, section 2.4,
   688  	// "The Yacas Book of Algorithms":
   689  	// http://yacas.sourceforge.net/Algo.book.pdf
   690  
   691  	var a, b, c Int
   692  	a.Set(x)
   693  	b.Set(y)
   694  	j := 1
   695  
   696  	if b.neg {
   697  		if a.neg {
   698  			j = -1
   699  		}
   700  		b.neg = false
   701  	}
   702  
   703  	for {
   704  		if b.Cmp(intOne) == 0 {
   705  			return j
   706  		}
   707  		if len(a.abs) == 0 {
   708  			return 0
   709  		}
   710  		a.Mod(&a, &b)
   711  		if len(a.abs) == 0 {
   712  			return 0
   713  		}
   714  		// a > 0
   715  
   716  		// handle factors of 2 in 'a'
   717  		s := a.abs.trailingZeroBits()
   718  		if s&1 != 0 {
   719  			bmod8 := b.abs[0] & 7
   720  			if bmod8 == 3 || bmod8 == 5 {
   721  				j = -j
   722  			}
   723  		}
   724  		c.Rsh(&a, s) // a = 2^s*c
   725  
   726  		// swap numerator and denominator
   727  		if b.abs[0]&3 == 3 && c.abs[0]&3 == 3 {
   728  			j = -j
   729  		}
   730  		a.Set(&b)
   731  		b.Set(&c)
   732  	}
   733  }
   734  
   735  // modSqrt3Mod4 uses the identity
   736  //      (a^((p+1)/4))^2  mod p
   737  //   == u^(p+1)          mod p
   738  //   == u^2              mod p
   739  // to calculate the square root of any quadratic residue mod p quickly for 3
   740  // mod 4 primes.
   741  func (z *Int) modSqrt3Mod4Prime(x, p *Int) *Int {
   742  	e := new(Int).Add(p, intOne) // e = p + 1
   743  	e.Rsh(e, 2)                  // e = (p + 1) / 4
   744  	z.Exp(x, e, p)               // z = x^e mod p
   745  	return z
   746  }
   747  
   748  // modSqrtTonelliShanks uses the Tonelli-Shanks algorithm to find the square
   749  // root of a quadratic residue modulo any prime.
   750  func (z *Int) modSqrtTonelliShanks(x, p *Int) *Int {
   751  	// Break p-1 into s*2^e such that s is odd.
   752  	var s Int
   753  	s.Sub(p, intOne)
   754  	e := s.abs.trailingZeroBits()
   755  	s.Rsh(&s, e)
   756  
   757  	// find some non-square n
   758  	var n Int
   759  	n.SetInt64(2)
   760  	for Jacobi(&n, p) != -1 {
   761  		n.Add(&n, intOne)
   762  	}
   763  
   764  	// Core of the Tonelli-Shanks algorithm. Follows the description in
   765  	// section 6 of "Square roots from 1; 24, 51, 10 to Dan Shanks" by Ezra
   766  	// Brown:
   767  	// https://www.maa.org/sites/default/files/pdf/upload_library/22/Polya/07468342.di020786.02p0470a.pdf
   768  	var y, b, g, t Int
   769  	y.Add(&s, intOne)
   770  	y.Rsh(&y, 1)
   771  	y.Exp(x, &y, p)  // y = x^((s+1)/2)
   772  	b.Exp(x, &s, p)  // b = x^s
   773  	g.Exp(&n, &s, p) // g = n^s
   774  	r := e
   775  	for {
   776  		// find the least m such that ord_p(b) = 2^m
   777  		var m uint
   778  		t.Set(&b)
   779  		for t.Cmp(intOne) != 0 {
   780  			t.Mul(&t, &t).Mod(&t, p)
   781  			m++
   782  		}
   783  
   784  		if m == 0 {
   785  			return z.Set(&y)
   786  		}
   787  
   788  		t.SetInt64(0).SetBit(&t, int(r-m-1), 1).Exp(&g, &t, p)
   789  		// t = g^(2^(r-m-1)) mod p
   790  		g.Mul(&t, &t).Mod(&g, p) // g = g^(2^(r-m)) mod p
   791  		y.Mul(&y, &t).Mod(&y, p)
   792  		b.Mul(&b, &g).Mod(&b, p)
   793  		r = m
   794  	}
   795  }
   796  
   797  // ModSqrt sets z to a square root of x mod p if such a square root exists, and
   798  // returns z. The modulus p must be an odd prime. If x is not a square mod p,
   799  // ModSqrt leaves z unchanged and returns nil. This function panics if p is
   800  // not an odd integer.
   801  func (z *Int) ModSqrt(x, p *Int) *Int {
   802  	switch Jacobi(x, p) {
   803  	case -1:
   804  		return nil // x is not a square mod p
   805  	case 0:
   806  		return z.SetInt64(0) // sqrt(0) mod p = 0
   807  	case 1:
   808  		break
   809  	}
   810  	if x.neg || x.Cmp(p) >= 0 { // ensure 0 <= x < p
   811  		x = new(Int).Mod(x, p)
   812  	}
   813  
   814  	// Check whether p is 3 mod 4, and if so, use the faster algorithm.
   815  	if len(p.abs) > 0 && p.abs[0]%4 == 3 {
   816  		return z.modSqrt3Mod4Prime(x, p)
   817  	}
   818  	// Otherwise, use Tonelli-Shanks.
   819  	return z.modSqrtTonelliShanks(x, p)
   820  }
   821  
   822  // Lsh sets z = x << n and returns z.
   823  func (z *Int) Lsh(x *Int, n uint) *Int {
   824  	z.abs = z.abs.shl(x.abs, n)
   825  	z.neg = x.neg
   826  	return z
   827  }
   828  
   829  // Rsh sets z = x >> n and returns z.
   830  func (z *Int) Rsh(x *Int, n uint) *Int {
   831  	if x.neg {
   832  		// (-x) >> s == ^(x-1) >> s == ^((x-1) >> s) == -(((x-1) >> s) + 1)
   833  		t := z.abs.sub(x.abs, natOne) // no underflow because |x| > 0
   834  		t = t.shr(t, n)
   835  		z.abs = t.add(t, natOne)
   836  		z.neg = true // z cannot be zero if x is negative
   837  		return z
   838  	}
   839  
   840  	z.abs = z.abs.shr(x.abs, n)
   841  	z.neg = false
   842  	return z
   843  }
   844  
   845  // Bit returns the value of the i'th bit of x. That is, it
   846  // returns (x>>i)&1. The bit index i must be >= 0.
   847  func (x *Int) Bit(i int) uint {
   848  	if i == 0 {
   849  		// optimization for common case: odd/even test of x
   850  		if len(x.abs) > 0 {
   851  			return uint(x.abs[0] & 1) // bit 0 is same for -x
   852  		}
   853  		return 0
   854  	}
   855  	if i < 0 {
   856  		panic("negative bit index")
   857  	}
   858  	if x.neg {
   859  		t := nat(nil).sub(x.abs, natOne)
   860  		return t.bit(uint(i)) ^ 1
   861  	}
   862  
   863  	return x.abs.bit(uint(i))
   864  }
   865  
   866  // SetBit sets z to x, with x's i'th bit set to b (0 or 1).
   867  // That is, if b is 1 SetBit sets z = x | (1 << i);
   868  // if b is 0 SetBit sets z = x &^ (1 << i). If b is not 0 or 1,
   869  // SetBit will panic.
   870  func (z *Int) SetBit(x *Int, i int, b uint) *Int {
   871  	if i < 0 {
   872  		panic("negative bit index")
   873  	}
   874  	if x.neg {
   875  		t := z.abs.sub(x.abs, natOne)
   876  		t = t.setBit(t, uint(i), b^1)
   877  		z.abs = t.add(t, natOne)
   878  		z.neg = len(z.abs) > 0
   879  		return z
   880  	}
   881  	z.abs = z.abs.setBit(x.abs, uint(i), b)
   882  	z.neg = false
   883  	return z
   884  }
   885  
   886  // And sets z = x & y and returns z.
   887  func (z *Int) And(x, y *Int) *Int {
   888  	if x.neg == y.neg {
   889  		if x.neg {
   890  			// (-x) & (-y) == ^(x-1) & ^(y-1) == ^((x-1) | (y-1)) == -(((x-1) | (y-1)) + 1)
   891  			x1 := nat(nil).sub(x.abs, natOne)
   892  			y1 := nat(nil).sub(y.abs, natOne)
   893  			z.abs = z.abs.add(z.abs.or(x1, y1), natOne)
   894  			z.neg = true // z cannot be zero if x and y are negative
   895  			return z
   896  		}
   897  
   898  		// x & y == x & y
   899  		z.abs = z.abs.and(x.abs, y.abs)
   900  		z.neg = false
   901  		return z
   902  	}
   903  
   904  	// x.neg != y.neg
   905  	if x.neg {
   906  		x, y = y, x // & is symmetric
   907  	}
   908  
   909  	// x & (-y) == x & ^(y-1) == x &^ (y-1)
   910  	y1 := nat(nil).sub(y.abs, natOne)
   911  	z.abs = z.abs.andNot(x.abs, y1)
   912  	z.neg = false
   913  	return z
   914  }
   915  
   916  // AndNot sets z = x &^ y and returns z.
   917  func (z *Int) AndNot(x, y *Int) *Int {
   918  	if x.neg == y.neg {
   919  		if x.neg {
   920  			// (-x) &^ (-y) == ^(x-1) &^ ^(y-1) == ^(x-1) & (y-1) == (y-1) &^ (x-1)
   921  			x1 := nat(nil).sub(x.abs, natOne)
   922  			y1 := nat(nil).sub(y.abs, natOne)
   923  			z.abs = z.abs.andNot(y1, x1)
   924  			z.neg = false
   925  			return z
   926  		}
   927  
   928  		// x &^ y == x &^ y
   929  		z.abs = z.abs.andNot(x.abs, y.abs)
   930  		z.neg = false
   931  		return z
   932  	}
   933  
   934  	if x.neg {
   935  		// (-x) &^ y == ^(x-1) &^ y == ^(x-1) & ^y == ^((x-1) | y) == -(((x-1) | y) + 1)
   936  		x1 := nat(nil).sub(x.abs, natOne)
   937  		z.abs = z.abs.add(z.abs.or(x1, y.abs), natOne)
   938  		z.neg = true // z cannot be zero if x is negative and y is positive
   939  		return z
   940  	}
   941  
   942  	// x &^ (-y) == x &^ ^(y-1) == x & (y-1)
   943  	y1 := nat(nil).sub(y.abs, natOne)
   944  	z.abs = z.abs.and(x.abs, y1)
   945  	z.neg = false
   946  	return z
   947  }
   948  
   949  // Or sets z = x | y and returns z.
   950  func (z *Int) Or(x, y *Int) *Int {
   951  	if x.neg == y.neg {
   952  		if x.neg {
   953  			// (-x) | (-y) == ^(x-1) | ^(y-1) == ^((x-1) & (y-1)) == -(((x-1) & (y-1)) + 1)
   954  			x1 := nat(nil).sub(x.abs, natOne)
   955  			y1 := nat(nil).sub(y.abs, natOne)
   956  			z.abs = z.abs.add(z.abs.and(x1, y1), natOne)
   957  			z.neg = true // z cannot be zero if x and y are negative
   958  			return z
   959  		}
   960  
   961  		// x | y == x | y
   962  		z.abs = z.abs.or(x.abs, y.abs)
   963  		z.neg = false
   964  		return z
   965  	}
   966  
   967  	// x.neg != y.neg
   968  	if x.neg {
   969  		x, y = y, x // | is symmetric
   970  	}
   971  
   972  	// x | (-y) == x | ^(y-1) == ^((y-1) &^ x) == -(^((y-1) &^ x) + 1)
   973  	y1 := nat(nil).sub(y.abs, natOne)
   974  	z.abs = z.abs.add(z.abs.andNot(y1, x.abs), natOne)
   975  	z.neg = true // z cannot be zero if one of x or y is negative
   976  	return z
   977  }
   978  
   979  // Xor sets z = x ^ y and returns z.
   980  func (z *Int) Xor(x, y *Int) *Int {
   981  	if x.neg == y.neg {
   982  		if x.neg {
   983  			// (-x) ^ (-y) == ^(x-1) ^ ^(y-1) == (x-1) ^ (y-1)
   984  			x1 := nat(nil).sub(x.abs, natOne)
   985  			y1 := nat(nil).sub(y.abs, natOne)
   986  			z.abs = z.abs.xor(x1, y1)
   987  			z.neg = false
   988  			return z
   989  		}
   990  
   991  		// x ^ y == x ^ y
   992  		z.abs = z.abs.xor(x.abs, y.abs)
   993  		z.neg = false
   994  		return z
   995  	}
   996  
   997  	// x.neg != y.neg
   998  	if x.neg {
   999  		x, y = y, x // ^ is symmetric
  1000  	}
  1001  
  1002  	// x ^ (-y) == x ^ ^(y-1) == ^(x ^ (y-1)) == -((x ^ (y-1)) + 1)
  1003  	y1 := nat(nil).sub(y.abs, natOne)
  1004  	z.abs = z.abs.add(z.abs.xor(x.abs, y1), natOne)
  1005  	z.neg = true // z cannot be zero if only one of x or y is negative
  1006  	return z
  1007  }
  1008  
  1009  // Not sets z = ^x and returns z.
  1010  func (z *Int) Not(x *Int) *Int {
  1011  	if x.neg {
  1012  		// ^(-x) == ^(^(x-1)) == x-1
  1013  		z.abs = z.abs.sub(x.abs, natOne)
  1014  		z.neg = false
  1015  		return z
  1016  	}
  1017  
  1018  	// ^x == -x-1 == -(x+1)
  1019  	z.abs = z.abs.add(x.abs, natOne)
  1020  	z.neg = true // z cannot be zero if x is positive
  1021  	return z
  1022  }
  1023  
  1024  // Sqrt sets z to ⌊√x⌋, the largest integer such that z² ≤ x, and returns z.
  1025  // It panics if x is negative.
  1026  func (z *Int) Sqrt(x *Int) *Int {
  1027  	if x.neg {
  1028  		panic("square root of negative number")
  1029  	}
  1030  	z.neg = false
  1031  	z.abs = z.abs.sqrt(x.abs)
  1032  	return z
  1033  }
  1034
View as plain text