1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
|
// 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.
func Prime(rand io.Reader, bits int) (p *big.Int, err error) {
if bits < 1 {
err = errors.New("crypto/rand: prime size must be positive")
}
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<<b) - 1)
// 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)
} 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 {
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
}
}
return
}
// Int returns a uniform random value in [0, max).
func Int(rand io.Reader, max *big.Int) (n *big.Int, err error) {
k := (max.BitLen() + 7) / 8
// b is the number of bits in the most significant byte of max.
b := uint(max.BitLen() % 8)
if b == 0 {
b = 8
}
bytes := make([]byte, k)
n = new(big.Int)
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
}
}
return
}
|
