1// Copyright 2020 ConsenSys Software Inc.
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
15// Code generated by consensys/gnark-crypto DO NOT EDIT
16
17package fptower
18
19import (
20	"github.com/consensys/gnark-crypto/ecc/bn254/fp"
21	"math/big"
22)
23
24// E2 is a degree two finite field extension of fp.Element
25type E2 struct {
26	A0, A1 fp.Element
27}
28
29// Equal returns true if z equals x, fasle otherwise
30func (z *E2) Equal(x *E2) bool {
31	return z.A0.Equal(&x.A0) && z.A1.Equal(&x.A1)
32}
33
34// Cmp compares (lexicographic order) z and x and returns:
35//
36//   -1 if z <  x
37//    0 if z == x
38//   +1 if z >  x
39//
40func (z *E2) Cmp(x *E2) int {
41	if a1 := z.A1.Cmp(&x.A1); a1 != 0 {
42		return a1
43	}
44	return z.A0.Cmp(&x.A0)
45}
46
47// LexicographicallyLargest returns true if this element is strictly lexicographically
48// larger than its negation, false otherwise
49func (z *E2) LexicographicallyLargest() bool {
50	// adapted from github.com/zkcrypto/bls12_381
51	if z.A1.IsZero() {
52		return z.A0.LexicographicallyLargest()
53	}
54	return z.A1.LexicographicallyLargest()
55}
56
57// SetString sets a E2 element from strings
58func (z *E2) SetString(s1, s2 string) *E2 {
59	z.A0.SetString(s1)
60	z.A1.SetString(s2)
61	return z
62}
63
64// SetZero sets an E2 elmt to zero
65func (z *E2) SetZero() *E2 {
66	z.A0.SetZero()
67	z.A1.SetZero()
68	return z
69}
70
71// Set sets an E2 from x
72func (z *E2) Set(x *E2) *E2 {
73	z.A0 = x.A0
74	z.A1 = x.A1
75	return z
76}
77
78// SetOne sets z to 1 in Montgomery form and returns z
79func (z *E2) SetOne() *E2 {
80	z.A0.SetOne()
81	z.A1.SetZero()
82	return z
83}
84
85// SetRandom sets a0 and a1 to random values
86func (z *E2) SetRandom() (*E2, error) {
87	if _, err := z.A0.SetRandom(); err != nil {
88		return nil, err
89	}
90	if _, err := z.A1.SetRandom(); err != nil {
91		return nil, err
92	}
93	return z, nil
94}
95
96// IsZero returns true if the two elements are equal, fasle otherwise
97func (z *E2) IsZero() bool {
98	return z.A0.IsZero() && z.A1.IsZero()
99}
100
101// Add adds two elements of E2
102func (z *E2) Add(x, y *E2) *E2 {
103	addE2(z, x, y)
104	return z
105}
106
107// Sub two elements of E2
108func (z *E2) Sub(x, y *E2) *E2 {
109	subE2(z, x, y)
110	return z
111}
112
113// Double doubles an E2 element
114func (z *E2) Double(x *E2) *E2 {
115	doubleE2(z, x)
116	return z
117}
118
119// Neg negates an E2 element
120func (z *E2) Neg(x *E2) *E2 {
121	negE2(z, x)
122	return z
123}
124
125// String implements Stringer interface for fancy printing
126func (z *E2) String() string {
127	return (z.A0.String() + "+" + z.A1.String() + "*u")
128}
129
130// ToMont converts to mont form
131func (z *E2) ToMont() *E2 {
132	z.A0.ToMont()
133	z.A1.ToMont()
134	return z
135}
136
137// FromMont converts from mont form
138func (z *E2) FromMont() *E2 {
139	z.A0.FromMont()
140	z.A1.FromMont()
141	return z
142}
143
144// MulByElement multiplies an element in E2 by an element in fp
145func (z *E2) MulByElement(x *E2, y *fp.Element) *E2 {
146	var yCopy fp.Element
147	yCopy.Set(y)
148	z.A0.Mul(&x.A0, &yCopy)
149	z.A1.Mul(&x.A1, &yCopy)
150	return z
151}
152
153// Conjugate conjugates an element in E2
154func (z *E2) Conjugate(x *E2) *E2 {
155	z.A0 = x.A0
156	z.A1.Neg(&x.A1)
157	return z
158}
159
160// Legendre returns the Legendre symbol of z
161func (z *E2) Legendre() int {
162	var n fp.Element
163	z.norm(&n)
164	return n.Legendre()
165}
166
167// Exp sets z=x**e and returns it
168func (z *E2) Exp(x E2, exponent *big.Int) *E2 {
169	z.SetOne()
170	b := exponent.Bytes()
171	for i := 0; i < len(b); i++ {
172		w := b[i]
173		for j := 0; j < 8; j++ {
174			z.Square(z)
175			if (w & (0b10000000 >> j)) != 0 {
176				z.Mul(z, &x)
177			}
178		}
179	}
180
181	return z
182}
183
184func init() {
185	q := fp.Modulus()
186	tmp := big.NewInt(3)
187	sqrtExp1.Set(q).Sub(&sqrtExp1, tmp).Rsh(&sqrtExp1, 2)
188
189	tmp.SetUint64(1)
190	sqrtExp2.Set(q).Sub(&sqrtExp2, tmp).Rsh(&sqrtExp2, 1)
191}
192
193var sqrtExp1, sqrtExp2 big.Int
194
195// Sqrt sets z to the square root of and returns z
196// The function does not test wether the square root
197// exists or not, it's up to the caller to call
198// Legendre beforehand.
199// cf https://eprint.iacr.org/2012/685.pdf (algo 9)
200func (z *E2) Sqrt(x *E2) *E2 {
201
202	var a1, alpha, b, x0, minusone E2
203
204	minusone.SetOne().Neg(&minusone)
205
206	a1.Exp(*x, &sqrtExp1)
207	alpha.Square(&a1).
208		Mul(&alpha, x)
209	x0.Mul(x, &a1)
210	if alpha.Equal(&minusone) {
211		var c fp.Element
212		c.Set(&x0.A0)
213		z.A0.Neg(&x0.A1)
214		z.A1.Set(&c)
215		return z
216	}
217	a1.SetOne()
218	b.Add(&a1, &alpha)
219
220	b.Exp(b, &sqrtExp2).Mul(&x0, &b)
221	z.Set(&b)
222	return z
223}
224