1// Copyright 2020 ConsenSys AG
2//
3// Licensed under the Apache License, Version 2.0 (the "License");
4// you may not use this file except in compliance with the License.
5// You may obtain a copy of the License at
6//
7//     http://www.apache.org/licenses/LICENSE-2.0
8//
9// Unless required by applicable law or agreed to in writing, software
10// distributed under the License is distributed on an "AS IS" BASIS,
11// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12// See the License for the specific language governing permissions and
13// limitations under the License.
14
15package fptower
16
17import (
18	"github.com/consensys/gnark-crypto/ecc/bw6-761/fp"
19)
20
21// E2 is a degree-two finite field extension of fp.Element
22type E2 struct {
23	A0, A1 fp.Element
24}
25
26// Equal returns true if z equals x, fasle otherwise
27func (z *E2) Equal(x *E2) bool {
28	return z.A0.Equal(&x.A0) && z.A1.Equal(&x.A1)
29}
30
31// SetString sets a E2 element from strings
32func (z *E2) SetString(s1, s2 string) *E2 {
33	z.A0.SetString(s1)
34	z.A1.SetString(s2)
35	return z
36}
37
38// SetZero sets an E2 elmt to zero
39func (z *E2) SetZero() *E2 {
40	z.A0.SetZero()
41	z.A1.SetZero()
42	return z
43}
44
45// Clone returns a copy of self
46func (z *E2) Clone() *E2 {
47	return &E2{
48		A0: z.A0,
49		A1: z.A1,
50	}
51}
52
53// Set sets an E2 from x
54func (z *E2) Set(x *E2) *E2 {
55	z.A0.Set(&x.A0)
56	z.A1.Set(&x.A1)
57	return z
58}
59
60// SetOne sets z to 1 in Montgomery form and returns z
61func (z *E2) SetOne() *E2 {
62	z.A0.SetOne()
63	z.A1.SetZero()
64	return z
65}
66
67// SetRandom sets a0 and a1 to random values
68func (z *E2) SetRandom() (*E2, error) {
69	if _, err := z.A0.SetRandom(); err != nil {
70		return nil, err
71	}
72	if _, err := z.A1.SetRandom(); err != nil {
73		return nil, err
74	}
75	return z, nil
76}
77
78// IsZero returns true if the two elements are equal, fasle otherwise
79func (z *E2) IsZero() bool {
80	return z.A0.IsZero() && z.A1.IsZero()
81}
82
83// Neg negates an E2 element
84func (z *E2) Neg(x *E2) *E2 {
85	z.A0.Neg(&x.A0)
86	z.A1.Neg(&x.A1)
87	return z
88}
89
90// String implements Stringer interface for fancy printing
91func (z *E2) String() string {
92	return (z.A0.String() + "+" + z.A1.String() + "*u")
93}
94
95// ToMont converts to mont form
96func (z *E2) ToMont() *E2 {
97	z.A0.ToMont()
98	z.A1.ToMont()
99	return z
100}
101
102// FromMont converts from mont form
103func (z *E2) FromMont() *E2 {
104	z.A0.FromMont()
105	z.A1.FromMont()
106	return z
107}
108
109// Add adds two elements of E2
110func (z *E2) Add(x, y *E2) *E2 {
111	z.A0.Add(&x.A0, &y.A0)
112	z.A1.Add(&x.A1, &y.A1)
113	return z
114}
115
116// Sub two elements of E2
117func (z *E2) Sub(x, y *E2) *E2 {
118	z.A0.Sub(&x.A0, &y.A0)
119	z.A1.Sub(&x.A1, &y.A1)
120	return z
121}
122
123// Double doubles an E2 element
124func (z *E2) Double(x *E2) *E2 {
125	z.A0.Double(&x.A0)
126	z.A1.Double(&x.A1)
127	return z
128}
129
130// Mul sets z to the E2-product of x,y, returns z
131func (z *E2) Mul(x, y *E2) *E2 {
132	var a, b, c fp.Element
133	a.Add(&x.A0, &x.A1)
134	b.Add(&y.A0, &y.A1)
135	a.Mul(&a, &b)
136	b.Mul(&x.A0, &y.A0)
137	c.Mul(&x.A1, &y.A1)
138	z.A1.Sub(&a, &b).Sub(&z.A1, &c)
139	z.A0.Double(&c).Double(&z.A0).Neg(&z.A0).Add(&z.A0, &b)
140	return z
141}
142
143// MulAssign sets z to the E2-product of z,x returns z
144func (z *E2) MulAssign(x *E2) *E2 {
145	var t E2
146	t.Mul(z, x)
147	z.Set(&t)
148	return z
149}
150
151// Square sets z to the E2-product of x,x returns z
152func (z *E2) Square(x *E2) *E2 {
153	// algo 22 https://eprint.iacr.org/2010/354.pdf
154	var c0, c2 fp.Element
155	c2.Double(&x.A1).Double(&c2).Neg(&c2).Add(&c2, &x.A0)
156	c0.Add(&x.A0, &x.A1)
157	c0.Mul(&c0, &c2) // (x1+x2)*(x1+(u**2)x2) = x1**2+(u**2)x2**2+(u**2+1)x1x2
158	c2.Mul(&x.A0, &x.A1)
159	z.A1.Double(&c2)
160	z.A0.Add(&c0, &z.A1).Add(&z.A0, &c2)
161	return z
162}
163
164// MulByNonResidue multiplies a E2 by (0,1)
165func (z *E2) MulByNonResidue(x *E2) *E2 {
166	a := x.A0
167	b := x.A1 // fetching x.A1 in the function below is slower
168	z.A0.Double(&b).Double(&z.A0).Neg(&z.A0)
169	z.A1 = a
170	return z
171}
172
173// Inverse sets z to the E2-inverse of x, returns z
174func (z *E2) Inverse(x *E2) *E2 {
175	// Algorithm 8 from https://eprint.iacr.org/2010/354.pdf
176	var t0, t1, tmp fp.Element
177	t0.Square(&x.A0)
178	t1.Square(&x.A1)
179	tmp.Double(&t1).Double(&tmp).Neg(&tmp)
180	t0.Sub(&t0, &tmp)
181	t1.Inverse(&t0)
182	z.A0.Mul(&x.A0, &t1)
183	z.A1.Mul(&x.A1, &t1).Neg(&z.A1)
184
185	return z
186}
187
188// MulByElement multiplies an element in E2 by an element in fp
189func (z *E2) MulByElement(x *E2, y *fp.Element) *E2 {
190	var yCopy fp.Element
191	yCopy.Set(y)
192	z.A0.Mul(&x.A0, &yCopy)
193	z.A1.Mul(&x.A1, &yCopy)
194	return z
195}
196
197// Conjugate conjugates an element in E2
198func (z *E2) Conjugate(x *E2) *E2 {
199	z.A0.Set(&x.A0)
200	z.A1.Neg(&x.A1)
201	return z
202}
203