1package fields
  2
  3import (
  4	"bytes"
  5	"math/big"
  6)
  7
  8// Fq12 uses the same algorithms than Fq2, but with [2][3][2]*big.Int data structure
  9
 10// Fq12 is Field 12
 11type Fq12 struct {
 12	F          Fq6
 13	Fq2        Fq2
 14	NonResidue [2]*big.Int
 15}
 16
 17// NewFq12 generates a new Fq12
 18func NewFq12(f Fq6, fq2 Fq2, nonResidue [2]*big.Int) Fq12 {
 19	fq12 := Fq12{
 20		f,
 21		fq2,
 22		nonResidue,
 23	}
 24	return fq12
 25}
 26
 27// Zero returns a Zero value on the Fq12
 28func (fq12 Fq12) Zero() [2][3][2]*big.Int {
 29	return [2][3][2]*big.Int{fq12.F.Zero(), fq12.F.Zero()}
 30}
 31
 32// One returns a One value on the Fq12
 33func (fq12 Fq12) One() [2][3][2]*big.Int {
 34	return [2][3][2]*big.Int{fq12.F.One(), fq12.F.Zero()}
 35}
 36
 37func (fq12 Fq12) mulByNonResidue(a [3][2]*big.Int) [3][2]*big.Int {
 38	return [3][2]*big.Int{
 39		fq12.Fq2.Mul(fq12.NonResidue, a[2]),
 40		a[0],
 41		a[1],
 42	}
 43}
 44
 45// Add performs an addition on the Fq12
 46func (fq12 Fq12) Add(a, b [2][3][2]*big.Int) [2][3][2]*big.Int {
 47	return [2][3][2]*big.Int{
 48		fq12.F.Add(a[0], b[0]),
 49		fq12.F.Add(a[1], b[1]),
 50	}
 51}
 52
 53// Double performs a doubling on the Fq12
 54func (fq12 Fq12) Double(a [2][3][2]*big.Int) [2][3][2]*big.Int {
 55	return fq12.Add(a, a)
 56}
 57
 58// Sub performs a subtraction on the Fq12
 59func (fq12 Fq12) Sub(a, b [2][3][2]*big.Int) [2][3][2]*big.Int {
 60	return [2][3][2]*big.Int{
 61		fq12.F.Sub(a[0], b[0]),
 62		fq12.F.Sub(a[1], b[1]),
 63	}
 64}
 65
 66// Neg performs a negation on the Fq12
 67func (fq12 Fq12) Neg(a [2][3][2]*big.Int) [2][3][2]*big.Int {
 68	return fq12.Sub(fq12.Zero(), a)
 69}
 70
 71// Mul performs a multiplication on the Fq12
 72func (fq12 Fq12) Mul(a, b [2][3][2]*big.Int) [2][3][2]*big.Int {
 73	// Multiplication and Squaring on Pairing-Friendly .pdf; Section 3 (Karatsuba)
 74	v0 := fq12.F.Mul(a[0], b[0])
 75	v1 := fq12.F.Mul(a[1], b[1])
 76	return [2][3][2]*big.Int{
 77		fq12.F.Add(v0, fq12.mulByNonResidue(v1)),
 78		fq12.F.Sub(
 79			fq12.F.Mul(
 80				fq12.F.Add(a[0], a[1]),
 81				fq12.F.Add(b[0], b[1])),
 82			fq12.F.Add(v0, v1)),
 83	}
 84}
 85
 86func (fq12 Fq12) MulScalar(base [2][3][2]*big.Int, e *big.Int) [2][3][2]*big.Int {
 87	// for more possible implementations see g2.go file, at the function g2.MulScalar()
 88
 89	res := fq12.Zero()
 90	rem := e
 91	exp := base
 92
 93	for !bytes.Equal(rem.Bytes(), big.NewInt(int64(0)).Bytes()) {
 94		// if rem % 2 == 1
 95		if bytes.Equal(new(big.Int).Rem(rem, big.NewInt(int64(2))).Bytes(), big.NewInt(int64(1)).Bytes()) {
 96			res = fq12.Add(res, exp)
 97		}
 98		exp = fq12.Double(exp)
 99		rem = rem.Rsh(rem, 1) // rem = rem >> 1
100	}
101	return res
102}
103
104// Inverse returns the inverse on the Fq12
105func (fq12 Fq12) Inverse(a [2][3][2]*big.Int) [2][3][2]*big.Int {
106	t0 := fq12.F.Square(a[0])
107	t1 := fq12.F.Square(a[1])
108	t2 := fq12.F.Sub(t0, fq12.mulByNonResidue(t1))
109	t3 := fq12.F.Inverse(t2)
110	return [2][3][2]*big.Int{
111		fq12.F.Mul(a[0], t3),
112		fq12.F.Neg(fq12.F.Mul(a[1], t3)),
113	}
114}
115
116// Div performs a division on the Fq12
117func (fq12 Fq12) Div(a, b [2][3][2]*big.Int) [2][3][2]*big.Int {
118	return fq12.Mul(a, fq12.Inverse(b))
119}
120
121// Square performs a square operation on the Fq12
122func (fq12 Fq12) Square(a [2][3][2]*big.Int) [2][3][2]*big.Int {
123	ab := fq12.F.Mul(a[0], a[1])
124
125	return [2][3][2]*big.Int{
126		fq12.F.Sub(
127			fq12.F.Mul(
128				fq12.F.Add(a[0], a[1]),
129				fq12.F.Add(
130					a[0],
131					fq12.mulByNonResidue(a[1]))),
132			fq12.F.Add(
133				ab,
134				fq12.mulByNonResidue(ab))),
135		fq12.F.Add(ab, ab),
136	}
137}
138
139func (fq12 Fq12) Exp(base [2][3][2]*big.Int, e *big.Int) [2][3][2]*big.Int {
140	// TODO fix bottleneck
141
142	res := fq12.One()
143	rem := fq12.Fq2.F.Copy(e)
144	exp := base
145
146	// before := time.Now()
147	for !bytes.Equal(rem.Bytes(), big.NewInt(int64(0)).Bytes()) {
148		if BigIsOdd(rem) {
149			res = fq12.Mul(res, exp)
150		}
151		exp = fq12.Square(exp)
152		rem = new(big.Int).Rsh(rem, 1)
153	}
154	// fmt.Println("time elapsed:", time.Since(before))
155	return res
156}
157func (fq12 Fq12) Affine(a [2][3][2]*big.Int) [2][3][2]*big.Int {
158	return [2][3][2]*big.Int{
159		fq12.F.Affine(a[0]),
160		fq12.F.Affine(a[1]),
161	}
162}
163func (fq12 Fq12) Equal(a, b [2][3][2]*big.Int) bool {
164	return fq12.F.Equal(a[0], b[0]) && fq12.F.Equal(a[1], b[1])
165}