-
Notifications
You must be signed in to change notification settings - Fork 0
/
precompute.go
100 lines (93 loc) · 2.24 KB
/
precompute.go
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
package precompute
import (
"context"
"math/big"
)
// const byteChunkSize = 125000
// Table is the precomputing table
type Table struct {
g *big.Int
n *big.Int
byteChunkSize int
table []*big.Int
}
// NewTable creates a new precomputing table
func NewTable(g, n, elementUpperBound *big.Int, numElements uint64, byteChunkSize int) *Table {
t := &Table{
g: g,
n: n,
byteChunkSize: byteChunkSize,
}
maxBitLen := elementUpperBound.BitLen() * int(numElements)
numByteChunks := maxBitLen / (t.byteChunkSize * 8)
t.table = make([]*big.Int, numByteChunks)
t.table[0] = new(big.Int).Set(g)
opt := new(big.Int).Lsh(big1, uint(t.byteChunkSize*8))
for i := 1; i < numByteChunks; i++ {
t.table[i] = new(big.Int).Exp(t.table[i-1], opt, n)
}
return t
}
// Compute computes the result of base^x mod n with specified number of goroutines
func (t *Table) Compute(x *big.Int, numRoutine int) *big.Int {
xBytes := x.Bytes()
inputChan := make(chan input, numRoutine<<2)
outputChan := make(chan *big.Int, numRoutine)
ctx, cancel := context.WithCancel(context.Background())
defer cancel()
for i := 0; i < numRoutine; i++ {
go t.routineCompute(ctx, t.n, xBytes, inputChan, outputChan)
}
resChan := make(chan *big.Int)
go func() {
res := big.NewInt(1)
counter := len(xBytes) / t.byteChunkSize
if len(xBytes)%t.byteChunkSize != 0 {
counter++
}
for out := range outputChan {
res.Mul(res, out)
res.Mod(res, t.n)
counter--
if counter == 0 {
resChan <- res
return
}
}
}()
for i := len(xBytes); i > 0; i -= t.byteChunkSize {
right := i
left := right - t.byteChunkSize
if left < 0 {
left = 0
}
idx := (len(xBytes) - i) / t.byteChunkSize
inputChan <- input{
left: left,
right: right,
tableIdx: idx,
}
}
return <-resChan
}
type input struct {
left int
right int
tableIdx int
}
func (t *Table) routineCompute(ctx context.Context, n *big.Int, xBytes []byte,
inputChan chan input, resChan chan *big.Int) {
opt := new(big.Int)
for {
select {
case <-ctx.Done():
return
case in := <-inputChan:
opt.SetBytes(xBytes[in.left:in.right])
res := new(big.Int).Exp(t.table[in.tableIdx], opt, n)
resChan <- res
default:
continue
}
}
}