/
mulexp.go
79 lines (72 loc) · 1.98 KB
/
mulexp.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
package accumulator
import (
"math/big"
"github.com/1e358/multiexp"
)
// SimpleExp should calculate g^x mod n.
// It is implemented here to campare with golang's official Exp and MultiExp
func SimpleExp(g, x, n *big.Int) *big.Int {
if g.Cmp(big1) <= 0 || n.Cmp(big1) <= 0 || x.Cmp(big1) < 0 {
panic("invalid input for function SimpleExp")
}
// change x to its binary representation
//binaryX := x.Bytes()
bitLen := x.BitLen()
//fmt.Println("BitLen = ", bitLen)
bits := x.Bits() // bits is a slice of uint32
//fmt.Println("Bitslice len = ", len(bits))
var mask uint
var gCopy, output big.Int
gCopy.Set(g)
output.SetInt64(1)
for i := 0; i < bitLen; i++ {
chunk := i / 64
for j := 0; j < 64; j++ {
mask = uint(1 << j)
if (uint(bits[chunk]) & mask) == mask {
output.Mul(&output, &gCopy)
output.Mod(&output, n)
}
gCopy.Mul(&gCopy, &gCopy)
gCopy.Mod(&gCopy, n)
}
i += 64
}
multiexp.DoubleExp(g, [2]*big.Int{g, g}, g)
return &output
}
// GCB calculates the greatest common binaries of a and b.
// For example, if a = 1011 (binary) and b = 1100,
// the return will be of 1000(binary)
func GCB(a, b *big.Int) *big.Int {
bitStringA := a.Bits()
bitStringB := b.Bits()
var maxBitLen int
if len(bitStringA) > len(bitStringB) {
maxBitLen = len(bitStringB)
} else {
maxBitLen = len(bitStringA)
}
bitStingsRet := make([]big.Word, maxBitLen)
for i := 0; i < maxBitLen; i++ {
bitStingsRet[i] = CommonBits(bitStringA[i], bitStringB[i])
bitStringA[i] = bitStringA[i] - bitStingsRet[i]
bitStringB[i] = bitStringB[i] - bitStingsRet[i]
}
var ret big.Int
ret.SetBits(bitStingsRet)
return &ret
}
// CommonBits calculates the greatest common binaries of a and b when they are uint.
func CommonBits(a, b big.Word) big.Word {
ret := uint(0)
var mask uint
for i := 0; i < 32; i++ {
mask = uint(1 << i)
if ((uint(a) & mask) == mask) && ((uint(b) & mask) == mask) {
//fmt.Println("i == ", i, "mask = ", mask)
ret = uint(ret) | mask
}
}
return big.Word(ret)
}