blob: 11b1a28ec50f65109e04cecde7969ce78d10453a [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 ( "crypto/internal/randutil" "errors" "io" "math/big" ) // Prime returns a number of the given bit length that 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) (*big.Int, error) { if bits < 2 { return nil, errors.New("crypto/rand: prime size must be at least 2-bit") } randutil.MaybeReadByte(rand) b := uint(bits % 8) if b == 0 { b = 8 } bytes := make([]byte, (bits+7)/8) p := new(big.Int) for { if _, err := io.ReadFull(rand, bytes); 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) if p.ProbablyPrime(20) { return p, nil } } } // 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<