Source file src/pkg/crypto/rand/util.go

     1	// Copyright 2011 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	package rand
     6	
     7	import (
     8		"errors"
     9		"io"
    10		"math/big"
    11	)
    12	
    13	// Prime returns a number, p, of the given size, such that p is prime
    14	// with high probability.
    15	func Prime(rand io.Reader, bits int) (p *big.Int, err error) {
    16		if bits < 1 {
    17			err = errors.New("crypto/rand: prime size must be positive")
    18		}
    19	
    20		b := uint(bits % 8)
    21		if b == 0 {
    22			b = 8
    23		}
    24	
    25		bytes := make([]byte, (bits+7)/8)
    26		p = new(big.Int)
    27	
    28		for {
    29			_, err = io.ReadFull(rand, bytes)
    30			if err != nil {
    31				return nil, err
    32			}
    33	
    34			// Clear bits in the first byte to make sure the candidate has a size <= bits.
    35			bytes[0] &= uint8(int(1<<b) - 1)
    36			// Don't let the value be too small, i.e, set the most significant bit.
    37			bytes[0] |= 1 << (b - 1)
    38			// Make the value odd since an even number this large certainly isn't prime.
    39			bytes[len(bytes)-1] |= 1
    40	
    41			p.SetBytes(bytes)
    42			if p.ProbablyPrime(20) {
    43				return
    44			}
    45		}
    46	
    47		return
    48	}
    49	
    50	// Int returns a uniform random value in [0, max).
    51	func Int(rand io.Reader, max *big.Int) (n *big.Int, err error) {
    52		k := (max.BitLen() + 7) / 8
    53	
    54		// b is the number of bits in the most significant byte of max.
    55		b := uint(max.BitLen() % 8)
    56		if b == 0 {
    57			b = 8
    58		}
    59	
    60		bytes := make([]byte, k)
    61		n = new(big.Int)
    62	
    63		for {
    64			_, err = io.ReadFull(rand, bytes)
    65			if err != nil {
    66				return nil, err
    67			}
    68	
    69			// Clear bits in the first byte to increase the probability
    70			// that the candidate is < max.
    71			bytes[0] &= uint8(int(1<<b) - 1)
    72	
    73			n.SetBytes(bytes)
    74			if n.Cmp(max) < 0 {
    75				return
    76			}
    77		}
    78	
    79		return
    80	}