diff options
Diffstat (limited to 'libgo/go/math/big/int.go')
| -rw-r--r-- | libgo/go/math/big/int.go | 128 |
1 files changed, 47 insertions, 81 deletions
diff --git a/libgo/go/math/big/int.go b/libgo/go/math/big/int.go index 65334e0ef55..67ab7042ffe 100644 --- a/libgo/go/math/big/int.go +++ b/libgo/go/math/big/int.go @@ -273,7 +273,7 @@ func (z *Int) Mod(x, y *Int) *Int { // DivMod implements Euclidean division and modulus (unlike Go): // // q = x div y such that -// m = x - y*q with 0 <= m < |q| +// 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 @@ -551,8 +551,11 @@ func (z *Int) binaryGCD(a, b *Int) *Int { } // ProbablyPrime performs n Miller-Rabin tests to check whether x is prime. -// If it returns true, x is prime with probability 1 - 1/4^n. -// If it returns false, x is not prime. n must be > 0. +// If x is prime, it returns true. +// If x is not prime, it returns false with probability at least 1 - ¼ⁿ. +// +// It is not suitable for judging primes that an adversary may have crafted +// to fool this test. func (x *Int) ProbablyPrime(n int) bool { if n <= 0 { panic("non-positive n for ProbablyPrime") @@ -640,23 +643,23 @@ func Jacobi(x, y *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. -func (z *Int) ModSqrt(x, p *Int) *Int { - switch Jacobi(x, p) { - case -1: - return nil // x is not a square mod p - case 0: - return z.SetInt64(0) // sqrt(0) mod p = 0 - case 1: - break - } - if x.neg || x.Cmp(p) >= 0 { // ensure 0 <= x < p - x = new(Int).Mod(x, p) - } +// 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 { + z.Set(p) // z = p + z.Add(z, intOne) // z = p + 1 + z.Rsh(z, 2) // z = (p + 1) / 4 + z.Exp(x, z, p) // z = x^z mod p + return z +} +// 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 { // Break p-1 into s*2^e such that s is odd. var s Int s.Sub(p, intOne) @@ -703,6 +706,31 @@ func (z *Int) ModSqrt(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. +func (z *Int) ModSqrt(x, p *Int) *Int { + switch Jacobi(x, p) { + case -1: + return nil // x is not a square mod p + case 0: + return z.SetInt64(0) // sqrt(0) mod p = 0 + case 1: + break + } + if x.neg || x.Cmp(p) >= 0 { // ensure 0 <= x < p + x = new(Int).Mod(x, p) + } + + // Check whether p is 3 mod 4, and if so, use the faster algorithm. + if len(p.abs) > 0 && p.abs[0]%4 == 3 { + return z.modSqrt3Mod4Prime(x, p) + } + // Otherwise, use Tonelli-Shanks. + return z.modSqrtTonelliShanks(x, p) +} + // Lsh sets z = x << n and returns z. func (z *Int) Lsh(x *Int, n uint) *Int { z.abs = z.abs.shl(x.abs, n) @@ -904,65 +932,3 @@ func (z *Int) Not(x *Int) *Int { z.neg = true // z cannot be zero if x is positive return z } - -// Gob codec version. Permits backward-compatible changes to the encoding. -const intGobVersion byte = 1 - -// GobEncode implements the gob.GobEncoder interface. -func (x *Int) GobEncode() ([]byte, error) { - if x == nil { - return nil, nil - } - buf := make([]byte, 1+len(x.abs)*_S) // extra byte for version and sign bit - i := x.abs.bytes(buf) - 1 // i >= 0 - b := intGobVersion << 1 // make space for sign bit - if x.neg { - b |= 1 - } - buf[i] = b - return buf[i:], nil -} - -// GobDecode implements the gob.GobDecoder interface. -func (z *Int) GobDecode(buf []byte) error { - if len(buf) == 0 { - // Other side sent a nil or default value. - *z = Int{} - return nil - } - b := buf[0] - if b>>1 != intGobVersion { - return fmt.Errorf("Int.GobDecode: encoding version %d not supported", b>>1) - } - z.neg = b&1 != 0 - z.abs = z.abs.setBytes(buf[1:]) - return nil -} - -// MarshalJSON implements the json.Marshaler interface. -func (z *Int) MarshalJSON() ([]byte, error) { - // TODO(gri): get rid of the []byte/string conversions - return []byte(z.String()), nil -} - -// UnmarshalJSON implements the json.Unmarshaler interface. -func (z *Int) UnmarshalJSON(text []byte) error { - // TODO(gri): get rid of the []byte/string conversions - if _, ok := z.SetString(string(text), 0); !ok { - return fmt.Errorf("math/big: cannot unmarshal %q into a *big.Int", text) - } - return nil -} - -// MarshalText implements the encoding.TextMarshaler interface. -func (z *Int) MarshalText() (text []byte, err error) { - return []byte(z.String()), nil -} - -// UnmarshalText implements the encoding.TextUnmarshaler interface. -func (z *Int) UnmarshalText(text []byte) error { - if _, ok := z.SetString(string(text), 0); !ok { - return fmt.Errorf("math/big: cannot unmarshal %q into a *big.Int", text) - } - return nil -} |