1// Copyright 2012 The Go Authors. All rights reserved.
2// Use of this source code is governed by a BSD-style
3// license that can be found in the LICENSE file.
4
5package bn256
6
7// For details of the algorithms used, see "Multiplication and Squaring on
8// Pairing-Friendly Fields, Devegili et al.
9// http://eprint.iacr.org/2006/471.pdf.
10
11import (
12	"math/big"
13)
14
15// gfP12 implements the field of size p¹² as a quadratic extension of gfP6
16// where ω²=τ.
17type gfP12 struct {
18	x, y *gfP6 // value is xω + y
19}
20
21func newGFp12(pool *bnPool) *gfP12 {
22	return &gfP12{newGFp6(pool), newGFp6(pool)}
23}
24
25func (e *gfP12) String() string {
26	return "(" + e.x.String() + "," + e.y.String() + ")"
27}
28
29func (e *gfP12) Put(pool *bnPool) {
30	e.x.Put(pool)
31	e.y.Put(pool)
32}
33
34func (e *gfP12) Set(a *gfP12) *gfP12 {
35	e.x.Set(a.x)
36	e.y.Set(a.y)
37	return e
38}
39
40func (e *gfP12) SetZero() *gfP12 {
41	e.x.SetZero()
42	e.y.SetZero()
43	return e
44}
45
46func (e *gfP12) SetOne() *gfP12 {
47	e.x.SetZero()
48	e.y.SetOne()
49	return e
50}
51
52func (e *gfP12) Minimal() {
53	e.x.Minimal()
54	e.y.Minimal()
55}
56
57func (e *gfP12) IsZero() bool {
58	e.Minimal()
59	return e.x.IsZero() && e.y.IsZero()
60}
61
62func (e *gfP12) IsOne() bool {
63	e.Minimal()
64	return e.x.IsZero() && e.y.IsOne()
65}
66
67func (e *gfP12) Conjugate(a *gfP12) *gfP12 {
68	e.x.Negative(a.x)
69	e.y.Set(a.y)
70	return a
71}
72
73func (e *gfP12) Negative(a *gfP12) *gfP12 {
74	e.x.Negative(a.x)
75	e.y.Negative(a.y)
76	return e
77}
78
79// Frobenius computes (xω+y)^p = x^p ω·ξ^((p-1)/6) + y^p
80func (e *gfP12) Frobenius(a *gfP12, pool *bnPool) *gfP12 {
81	e.x.Frobenius(a.x, pool)
82	e.y.Frobenius(a.y, pool)
83	e.x.MulScalar(e.x, xiToPMinus1Over6, pool)
84	return e
85}
86
87// FrobeniusP2 computes (xω+y)^p² = x^p² ω·ξ^((p²-1)/6) + y^p²
88func (e *gfP12) FrobeniusP2(a *gfP12, pool *bnPool) *gfP12 {
89	e.x.FrobeniusP2(a.x)
90	e.x.MulGFP(e.x, xiToPSquaredMinus1Over6)
91	e.y.FrobeniusP2(a.y)
92	return e
93}
94
95func (e *gfP12) Add(a, b *gfP12) *gfP12 {
96	e.x.Add(a.x, b.x)
97	e.y.Add(a.y, b.y)
98	return e
99}
100
101func (e *gfP12) Sub(a, b *gfP12) *gfP12 {
102	e.x.Sub(a.x, b.x)
103	e.y.Sub(a.y, b.y)
104	return e
105}
106
107func (e *gfP12) Mul(a, b *gfP12, pool *bnPool) *gfP12 {
108	tx := newGFp6(pool)
109	tx.Mul(a.x, b.y, pool)
110	t := newGFp6(pool)
111	t.Mul(b.x, a.y, pool)
112	tx.Add(tx, t)
113
114	ty := newGFp6(pool)
115	ty.Mul(a.y, b.y, pool)
116	t.Mul(a.x, b.x, pool)
117	t.MulTau(t, pool)
118	e.y.Add(ty, t)
119	e.x.Set(tx)
120
121	tx.Put(pool)
122	ty.Put(pool)
123	t.Put(pool)
124	return e
125}
126
127func (e *gfP12) MulScalar(a *gfP12, b *gfP6, pool *bnPool) *gfP12 {
128	e.x.Mul(a.x, b, pool)
129	e.y.Mul(a.y, b, pool)
130	return e
131}
132
133func (c *gfP12) Exp(a *gfP12, power *big.Int, pool *bnPool) *gfP12 {
134	sum := newGFp12(pool)
135	sum.SetOne()
136	t := newGFp12(pool)
137
138	for i := power.BitLen() - 1; i >= 0; i-- {
139		t.Square(sum, pool)
140		if power.Bit(i) != 0 {
141			sum.Mul(t, a, pool)
142		} else {
143			sum.Set(t)
144		}
145	}
146
147	c.Set(sum)
148
149	sum.Put(pool)
150	t.Put(pool)
151
152	return c
153}
154
155func (e *gfP12) Square(a *gfP12, pool *bnPool) *gfP12 {
156	// Complex squaring algorithm
157	v0 := newGFp6(pool)
158	v0.Mul(a.x, a.y, pool)
159
160	t := newGFp6(pool)
161	t.MulTau(a.x, pool)
162	t.Add(a.y, t)
163	ty := newGFp6(pool)
164	ty.Add(a.x, a.y)
165	ty.Mul(ty, t, pool)
166	ty.Sub(ty, v0)
167	t.MulTau(v0, pool)
168	ty.Sub(ty, t)
169
170	e.y.Set(ty)
171	e.x.Double(v0)
172
173	v0.Put(pool)
174	t.Put(pool)
175	ty.Put(pool)
176
177	return e
178}
179
180func (e *gfP12) Invert(a *gfP12, pool *bnPool) *gfP12 {
181	// See "Implementing cryptographic pairings", M. Scott, section 3.2.
182	// ftp://136.206.11.249/pub/crypto/pairings.pdf
183	t1 := newGFp6(pool)
184	t2 := newGFp6(pool)
185
186	t1.Square(a.x, pool)
187	t2.Square(a.y, pool)
188	t1.MulTau(t1, pool)
189	t1.Sub(t2, t1)
190	t2.Invert(t1, pool)
191
192	e.x.Negative(a.x)
193	e.y.Set(a.y)
194	e.MulScalar(e, t2, pool)
195
196	t1.Put(pool)
197	t2.Put(pool)
198
199	return e
200}
201