1// Copyright 2020 The go-ethereum Authors
2// This file is part of the go-ethereum library.
3//
4// The go-ethereum library is free software: you can redistribute it and/or modify
5// it under the terms of the GNU Lesser General Public License as published by
6// the Free Software Foundation, either version 3 of the License, or
7// (at your option) any later version.
8//
9// The go-ethereum library is distributed in the hope that it will be useful,
10// but WITHOUT ANY WARRANTY; without even the implied warranty of
11// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12// GNU Lesser General Public License for more details.
13//
14// You should have received a copy of the GNU Lesser General Public License
15// along with the go-ethereum library. If not, see <http://www.gnu.org/licenses/>.
16
17package bls12381
18
19import (
20	"errors"
21	"math/big"
22)
23
24type fp2Temp struct {
25	t [4]*fe
26}
27
28type fp2 struct {
29	fp2Temp
30}
31
32func newFp2Temp() fp2Temp {
33	t := [4]*fe{}
34	for i := 0; i < len(t); i++ {
35		t[i] = &fe{}
36	}
37	return fp2Temp{t}
38}
39
40func newFp2() *fp2 {
41	t := newFp2Temp()
42	return &fp2{t}
43}
44
45func (e *fp2) fromBytes(in []byte) (*fe2, error) {
46	if len(in) != 96 {
47		return nil, errors.New("length of input string should be 96 bytes")
48	}
49	c1, err := fromBytes(in[:48])
50	if err != nil {
51		return nil, err
52	}
53	c0, err := fromBytes(in[48:])
54	if err != nil {
55		return nil, err
56	}
57	return &fe2{*c0, *c1}, nil
58}
59
60func (e *fp2) toBytes(a *fe2) []byte {
61	out := make([]byte, 96)
62	copy(out[:48], toBytes(&a[1]))
63	copy(out[48:], toBytes(&a[0]))
64	return out
65}
66
67func (e *fp2) new() *fe2 {
68	return new(fe2).zero()
69}
70
71func (e *fp2) zero() *fe2 {
72	return new(fe2).zero()
73}
74
75func (e *fp2) one() *fe2 {
76	return new(fe2).one()
77}
78
79func (e *fp2) add(c, a, b *fe2) {
80	add(&c[0], &a[0], &b[0])
81	add(&c[1], &a[1], &b[1])
82}
83
84func (e *fp2) addAssign(a, b *fe2) {
85	addAssign(&a[0], &b[0])
86	addAssign(&a[1], &b[1])
87}
88
89func (e *fp2) ladd(c, a, b *fe2) {
90	ladd(&c[0], &a[0], &b[0])
91	ladd(&c[1], &a[1], &b[1])
92}
93
94func (e *fp2) double(c, a *fe2) {
95	double(&c[0], &a[0])
96	double(&c[1], &a[1])
97}
98
99func (e *fp2) doubleAssign(a *fe2) {
100	doubleAssign(&a[0])
101	doubleAssign(&a[1])
102}
103
104func (e *fp2) ldouble(c, a *fe2) {
105	ldouble(&c[0], &a[0])
106	ldouble(&c[1], &a[1])
107}
108
109func (e *fp2) sub(c, a, b *fe2) {
110	sub(&c[0], &a[0], &b[0])
111	sub(&c[1], &a[1], &b[1])
112}
113
114func (e *fp2) subAssign(c, a *fe2) {
115	subAssign(&c[0], &a[0])
116	subAssign(&c[1], &a[1])
117}
118
119func (e *fp2) neg(c, a *fe2) {
120	neg(&c[0], &a[0])
121	neg(&c[1], &a[1])
122}
123
124func (e *fp2) mul(c, a, b *fe2) {
125	t := e.t
126	mul(t[1], &a[0], &b[0])
127	mul(t[2], &a[1], &b[1])
128	add(t[0], &a[0], &a[1])
129	add(t[3], &b[0], &b[1])
130	sub(&c[0], t[1], t[2])
131	addAssign(t[1], t[2])
132	mul(t[0], t[0], t[3])
133	sub(&c[1], t[0], t[1])
134}
135
136func (e *fp2) mulAssign(a, b *fe2) {
137	t := e.t
138	mul(t[1], &a[0], &b[0])
139	mul(t[2], &a[1], &b[1])
140	add(t[0], &a[0], &a[1])
141	add(t[3], &b[0], &b[1])
142	sub(&a[0], t[1], t[2])
143	addAssign(t[1], t[2])
144	mul(t[0], t[0], t[3])
145	sub(&a[1], t[0], t[1])
146}
147
148func (e *fp2) square(c, a *fe2) {
149	t := e.t
150	ladd(t[0], &a[0], &a[1])
151	sub(t[1], &a[0], &a[1])
152	ldouble(t[2], &a[0])
153	mul(&c[0], t[0], t[1])
154	mul(&c[1], t[2], &a[1])
155}
156
157func (e *fp2) squareAssign(a *fe2) {
158	t := e.t
159	ladd(t[0], &a[0], &a[1])
160	sub(t[1], &a[0], &a[1])
161	ldouble(t[2], &a[0])
162	mul(&a[0], t[0], t[1])
163	mul(&a[1], t[2], &a[1])
164}
165
166func (e *fp2) mulByNonResidue(c, a *fe2) {
167	t := e.t
168	sub(t[0], &a[0], &a[1])
169	add(&c[1], &a[0], &a[1])
170	c[0].set(t[0])
171}
172
173func (e *fp2) mulByB(c, a *fe2) {
174	t := e.t
175	double(t[0], &a[0])
176	double(t[1], &a[1])
177	doubleAssign(t[0])
178	doubleAssign(t[1])
179	sub(&c[0], t[0], t[1])
180	add(&c[1], t[0], t[1])
181}
182
183func (e *fp2) inverse(c, a *fe2) {
184	t := e.t
185	square(t[0], &a[0])
186	square(t[1], &a[1])
187	addAssign(t[0], t[1])
188	inverse(t[0], t[0])
189	mul(&c[0], &a[0], t[0])
190	mul(t[0], t[0], &a[1])
191	neg(&c[1], t[0])
192}
193
194func (e *fp2) mulByFq(c, a *fe2, b *fe) {
195	mul(&c[0], &a[0], b)
196	mul(&c[1], &a[1], b)
197}
198
199func (e *fp2) exp(c, a *fe2, s *big.Int) {
200	z := e.one()
201	for i := s.BitLen() - 1; i >= 0; i-- {
202		e.square(z, z)
203		if s.Bit(i) == 1 {
204			e.mul(z, z, a)
205		}
206	}
207	c.set(z)
208}
209
210func (e *fp2) frobeniusMap(c, a *fe2, power uint) {
211	c[0].set(&a[0])
212	if power%2 == 1 {
213		neg(&c[1], &a[1])
214		return
215	}
216	c[1].set(&a[1])
217}
218
219func (e *fp2) frobeniusMapAssign(a *fe2, power uint) {
220	if power%2 == 1 {
221		neg(&a[1], &a[1])
222		return
223	}
224}
225
226func (e *fp2) sqrt(c, a *fe2) bool {
227	u, x0, a1, alpha := &fe2{}, &fe2{}, &fe2{}, &fe2{}
228	u.set(a)
229	e.exp(a1, a, pMinus3Over4)
230	e.square(alpha, a1)
231	e.mul(alpha, alpha, a)
232	e.mul(x0, a1, a)
233	if alpha.equal(negativeOne2) {
234		neg(&c[0], &x0[1])
235		c[1].set(&x0[0])
236		return true
237	}
238	e.add(alpha, alpha, e.one())
239	e.exp(alpha, alpha, pMinus1Over2)
240	e.mul(c, alpha, x0)
241	e.square(alpha, c)
242	return alpha.equal(u)
243}
244
245func (e *fp2) isQuadraticNonResidue(a *fe2) bool {
246	// https://github.com/leovt/constructible/wiki/Taking-Square-Roots-in-quadratic-extension-Fields
247	c0, c1 := new(fe), new(fe)
248	square(c0, &a[0])
249	square(c1, &a[1])
250	add(c1, c1, c0)
251	return isQuadraticNonResidue(c1)
252}
253