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