Source: util.go in package crypto/rand


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.

Don't let the value be too small, i.e, set the most significant two bits. Setting the top two bits, rather than just the top bit, means that when two of these values are multiplied together, the result isn't ever one bit short.

		if b >= 2 {
			bytes[0] |= 3 << (b - 2)

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)

bitLen is the maximum bit length needed to encode a value < max.

	bitLen := n.BitLen()

the only valid result is 0

		return

k is the maximum byte length needed to encode a value < max.

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<<b) - 1)

		n.SetBytes(bytes)
		if n.Cmp(max) < 0 {
			return
		}
	}