forked from arnaucube/go-snark-study
/
fq2.go
154 lines (134 loc) · 3.41 KB
/
fq2.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
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
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
package fields
import (
"math/big"
)
// Fq2 is Field 2
type Fq2 struct {
F Fq
NonResidue *big.Int
}
// NewFq2 generates a new Fq2
func NewFq2(f Fq, nonResidue *big.Int) Fq2 {
fq2 := Fq2{
f,
nonResidue,
}
return fq2
}
// Zero returns a Zero value on the Fq2
func (fq2 Fq2) Zero() [2]*big.Int {
return [2]*big.Int{fq2.F.Zero(), fq2.F.Zero()}
}
// One returns a One value on the Fq2
func (fq2 Fq2) One() [2]*big.Int {
return [2]*big.Int{fq2.F.One(), fq2.F.Zero()}
}
func (fq2 Fq2) mulByNonResidue(a *big.Int) *big.Int {
return fq2.F.Mul(fq2.NonResidue, a)
}
// Add performs an addition on the Fq2
func (fq2 Fq2) Add(a, b [2]*big.Int) [2]*big.Int {
return [2]*big.Int{
fq2.F.Add(a[0], b[0]),
fq2.F.Add(a[1], b[1]),
}
}
// Double performs a doubling on the Fq2
func (fq2 Fq2) Double(a [2]*big.Int) [2]*big.Int {
return fq2.Add(a, a)
}
// Sub performs a subtraction on the Fq2
func (fq2 Fq2) Sub(a, b [2]*big.Int) [2]*big.Int {
return [2]*big.Int{
fq2.F.Sub(a[0], b[0]),
fq2.F.Sub(a[1], b[1]),
}
}
// Neg performs a negation on the Fq2
func (fq2 Fq2) Neg(a [2]*big.Int) [2]*big.Int {
return fq2.Sub(fq2.Zero(), a)
}
// Mul performs a multiplication on the Fq2
func (fq2 Fq2) Mul(a, b [2]*big.Int) [2]*big.Int {
// Multiplication and Squaring on Pairing-Friendly.pdf; Section 3 (Karatsuba)
// https://pdfs.semanticscholar.org/3e01/de88d7428076b2547b60072088507d881bf1.pdf
v0 := fq2.F.Mul(a[0], b[0])
v1 := fq2.F.Mul(a[1], b[1])
return [2]*big.Int{
fq2.F.Add(v0, fq2.mulByNonResidue(v1)),
fq2.F.Sub(
fq2.F.Mul(
fq2.F.Add(a[0], a[1]),
fq2.F.Add(b[0], b[1])),
fq2.F.Add(v0, v1)),
}
}
func (fq2 Fq2) MulScalar(p [2]*big.Int, e *big.Int) [2]*big.Int {
// for more possible implementations see g2.go file, at the function g2.MulScalar()
q := fq2.Zero()
d := fq2.F.Copy(e)
r := p
foundone := false
for i := d.BitLen(); i >= 0; i-- {
if foundone {
q = fq2.Double(q)
}
if d.Bit(i) == 1 {
foundone = true
q = fq2.Add(q, r)
}
}
return q
}
// Inverse returns the inverse on the Fq2
func (fq2 Fq2) Inverse(a [2]*big.Int) [2]*big.Int {
// High-Speed Software Implementation of the Optimal Ate Pairing over Barreto–Naehrig Curves .pdf
// https://eprint.iacr.org/2010/354.pdf , algorithm 8
t0 := fq2.F.Square(a[0])
t1 := fq2.F.Square(a[1])
t2 := fq2.F.Sub(t0, fq2.mulByNonResidue(t1))
t3 := fq2.F.Inverse(t2)
return [2]*big.Int{
fq2.F.Mul(a[0], t3),
fq2.F.Neg(fq2.F.Mul(a[1], t3)),
}
}
// Div performs a division on the Fq2
func (fq2 Fq2) Div(a, b [2]*big.Int) [2]*big.Int {
return fq2.Mul(a, fq2.Inverse(b))
}
// Square performs a square operation on the Fq2
func (fq2 Fq2) Square(a [2]*big.Int) [2]*big.Int {
// https://pdfs.semanticscholar.org/3e01/de88d7428076b2547b60072088507d881bf1.pdf , complex squaring
ab := fq2.F.Mul(a[0], a[1])
return [2]*big.Int{
fq2.F.Sub(
fq2.F.Mul(
fq2.F.Add(a[0], a[1]),
fq2.F.Add(
a[0],
fq2.mulByNonResidue(a[1]))),
fq2.F.Add(
ab,
fq2.mulByNonResidue(ab))),
fq2.F.Add(ab, ab),
}
}
func (fq2 Fq2) IsZero(a [2]*big.Int) bool {
return fq2.F.IsZero(a[0]) && fq2.F.IsZero(a[1])
}
func (fq2 Fq2) Affine(a [2]*big.Int) [2]*big.Int {
return [2]*big.Int{
fq2.F.Affine(a[0]),
fq2.F.Affine(a[1]),
}
}
func (fq2 Fq2) Equal(a, b [2]*big.Int) bool {
return fq2.F.Equal(a[0], b[0]) && fq2.F.Equal(a[1], b[1])
}
func (fq2 Fq2) Copy(a [2]*big.Int) [2]*big.Int {
return [2]*big.Int{
fq2.F.Copy(a[0]),
fq2.F.Copy(a[1]),
}
}