blob: 4dd171120341f13b5aa7517a04de453011441104 [file] [log] [blame]
 // Copyright 2011 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. package rand import ( "errors" "io" "math/big" ) // smallPrimes is a list of small, prime numbers that allows us to rapidly // exclude some fraction of composite candidates when searching for a random // prime. This list is truncated at the point where smallPrimesProduct exceeds // a uint64. It does not include two because we ensure that the candidates are // odd by construction. var smallPrimes = []uint8{ 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, } // smallPrimesProduct is the product of the values in smallPrimes and allows us // to reduce a candidate prime by this number and then determine whether it's // coprime to all the elements of smallPrimes without further big.Int // operations. var smallPrimesProduct = new(big.Int).SetUint64(16294579238595022365) // Prime returns a number, p, of the given size, such that p is prime // with high probability. // Prime will return error for any error returned by rand.Read or if bits < 2. func Prime(rand io.Reader, bits int) (p *big.Int, err error) { if bits < 2 { err = errors.New("crypto/rand: prime size must be at least 2-bit") return } b := uint(bits % 8) if b == 0 { b = 8 } bytes := make([]byte, (bits+7)/8) p = new(big.Int) bigMod := new(big.Int) for { _, err = io.ReadFull(rand, bytes) if err != nil { return nil, err } // Clear bits in the first byte to make sure the candidate has a size <= bits. bytes[0] &= uint8(int(1<= 2 { bytes[0] |= 3 << (b - 2) } else { // Here b==1, because b cannot be zero. bytes[0] |= 1 if len(bytes) > 1 { bytes[1] |= 0x80 } } // Make the value odd since an even number this large certainly isn't prime. bytes[len(bytes)-1] |= 1 p.SetBytes(bytes) // Calculate the value mod the product of smallPrimes. If it's // a multiple of any of these primes we add two until it isn't. // The probability of overflowing is minimal and can be ignored // because we still perform Miller-Rabin tests on the result. bigMod.Mod(p, smallPrimesProduct) mod := bigMod.Uint64() NextDelta: for delta := uint64(0); delta < 1<<20; delta += 2 { m := mod + delta for _, prime := range smallPrimes { if m%uint64(prime) == 0 && (bits > 6 || m != uint64(prime)) { continue NextDelta } } if delta > 0 { bigMod.SetUint64(delta) p.Add(p, bigMod) } break } // There is a tiny possibility that, by adding delta, we caused // the number to be one bit too long. Thus we check BitLen // here. if p.ProbablyPrime(20) && p.BitLen() == bits { return } } } // Int returns a uniform random value in [0, max). It panics if max <= 0. func Int(rand io.Reader, max *big.Int) (n *big.Int, err error) { if max.Sign() <= 0 { panic("crypto/rand: argument to Int is <= 0") } n = new(big.Int) n.Sub(max, n.SetUint64(1)) // bitLen is the maximum bit length needed to encode a value < max. bitLen := n.BitLen() if bitLen == 0 { // the only valid result is 0 return } // k is the maximum byte length needed to encode a value < max. k := (bitLen + 7) / 8 // b is the number of bits in the most significant byte of max-1. b := uint(bitLen % 8) if b == 0 { b = 8 } bytes := make([]byte, k) for { _, err = io.ReadFull(rand, bytes) if err != nil { return nil, err } // Clear bits in the first byte to increase the probability // that the candidate is < max. bytes[0] &= uint8(int(1<