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.
13 // smallPrimes is a list of small, prime numbers that allows us to rapidly
14 // exclude some fraction of composite candidates when searching for a random
15 // prime. This list is truncated at the point where smallPrimesProduct exceeds
16 // a uint64. It does not include two because we ensure that the candidates are
17 // odd by construction.
18 var smallPrimes
= []uint8{
19 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53,
22 // smallPrimesProduct is the product of the values in smallPrimes and allows us
23 // to reduce a candidate prime by this number and then determine whether it's
24 // coprime to all the elements of smallPrimes without further big.Int
26 var smallPrimesProduct
= new(big
.Int
).SetUint64(16294579238595022365)
28 // Prime returns a number, p, of the given size, such that p is prime
29 // with high probability.
30 func Prime(rand io
.Reader
, bits
int) (p
*big
.Int
, err error
) {
32 err
= errors
.New("crypto/rand: prime size must be positive")
40 bytes
:= make([]byte, (bits
+7)/8)
43 bigMod
:= new(big
.Int
)
46 _
, err
= io
.ReadFull(rand
, bytes
)
51 // Clear bits in the first byte to make sure the candidate has a size <= bits.
52 bytes
[0] &= uint8(int(1<<b
) - 1)
53 // Don't let the value be too small, i.e, set the most significant two bits.
54 // Setting the top two bits, rather than just the top bit,
55 // means that when two of these values are multiplied together,
56 // the result isn't ever one bit short.
58 bytes
[0] |
= 3 << (b
- 2)
60 // Here b==1, because b cannot be zero.
66 // Make the value odd since an even number this large certainly isn't prime.
67 bytes
[len(bytes
)-1] |
= 1
71 // Calculate the value mod the product of smallPrimes. If it's
72 // a multiple of any of these primes we add two until it isn't.
73 // The probability of overflowing is minimal and can be ignored
74 // because we still perform Miller-Rabin tests on the result.
75 bigMod
.Mod(p
, smallPrimesProduct
)
76 mod
:= bigMod
.Uint64()
79 for delta
:= uint64(0); delta
< 1<<20; delta
+= 2 {
81 for _
, prime
:= range smallPrimes
{
82 if m%uint
64(prime
) == 0 {
88 bigMod
.SetUint64(delta
)
94 // There is a tiny possibility that, by adding delta, we caused
95 // the number to be one bit too long. Thus we check BitLen
97 if p
.ProbablyPrime(20) && p
.BitLen() == bits
{
103 // Int returns a uniform random value in [0, max). It panics if max <= 0.
104 func Int(rand io
.Reader
, max
*big
.Int
) (n
*big
.Int
, err error
) {
106 panic("crypto/rand: argument to Int is <= 0")
108 k
:= (max
.BitLen() + 7) / 8
110 // b is the number of bits in the most significant byte of max.
111 b
:= uint(max
.BitLen() % 8)
116 bytes
:= make([]byte, k
)
120 _
, err
= io
.ReadFull(rand
, bytes
)
125 // Clear bits in the first byte to increase the probability
126 // that the candidate is < max.
127 bytes
[0] &= uint8(int(1<<b
) - 1)