1use core::ops::{Add, Mul, Neg, Sub};
2use rand::Rng;
3use crate::fields::{const_fq, FieldElement, Fq, Fq2, Fq6};
4use crate::arith::U256;
5
6fn frobenius_coeffs_c1(power: usize) -> Fq2 {
7 match power % 12 {
8 0 => Fq2::one(),
9 1 => Fq2::new(
10 const_fq([
11 12653890742059813127,
12 14585784200204367754,
13 1278438861261381767,
14 212598772761311868,
15 ]),
16 const_fq([
17 11683091849979440498,
18 14992204589386555739,
19 15866167890766973222,
20 1200023580730561873,
21 ]),
22 ),
23 2 => Fq2::new(
24 const_fq([
25 14595462726357228530,
26 17349508522658994025,
27 1017833795229664280,
28 299787779797702374,
29 ]),
30 Fq::zero(),
31 ),
32 3 => Fq2::new(
33 const_fq([
34 3914496794763385213,
35 790120733010914719,
36 7322192392869644725,
37 581366264293887267,
38 ]),
39 const_fq([
40 12817045492518885689,
41 4440270538777280383,
42 11178533038884588256,
43 2767537931541304486,
44 ]),
45 ),
46 _ => unimplemented!(),
47 }
48}
49
50#[derive(Copy, Clone, Debug, PartialEq, Eq)]
51#[repr(C)]
52pub struct Fq12 {
53 c0: Fq6,
54 c1: Fq6,
55}
56
57impl Fq12 {
58 pub fn new(c0: Fq6, c1: Fq6) -> Self {
59 Fq12 { c0: c0, c1: c1 }
60 }
61
62 fn final_exponentiation_first_chunk(&self) -> Option<Fq12> {
63 match self.inverse() {
64 Some(b) => {
65 let a = self.unitary_inverse();
66 let c = a * b;
67 let d = c.frobenius_map(2);
68
69 Some(d * c)
70 }
71 None => None,
72 }
73 }
74
75 fn final_exponentiation_last_chunk(&self) -> Fq12 {
76 let a = self.exp_by_neg_z();
77 let b = a.cyclotomic_squared();
78 let c = b.cyclotomic_squared();
79 let d = c * b;
80
81 let e = d.exp_by_neg_z();
82 let f = e.cyclotomic_squared();
83 let g = f.exp_by_neg_z();
84 let h = d.unitary_inverse();
85 let i = g.unitary_inverse();
86
87 let j = i * e;
88 let k = j * h;
89 let l = k * b;
90 let m = k * e;
91 let n = *self * m;
92
93 let o = l.frobenius_map(1);
94 let p = o * n;
95
96 let q = k.frobenius_map(2);
97 let r = q * p;
98
99 let s = self.unitary_inverse();
100 let t = s * l;
101 let u = t.frobenius_map(3);
102 let v = u * r;
103
104 v
105 }
106
107 pub fn final_exponentiation(&self) -> Option<Fq12> {
108 self.final_exponentiation_first_chunk()
109 .map(|a| a.final_exponentiation_last_chunk())
110 }
111
112 pub fn frobenius_map(&self, power: usize) -> Self {
113 Fq12 {
114 c0: self.c0.frobenius_map(power),
115 c1: self.c1
116 .frobenius_map(power)
117 .scale(frobenius_coeffs_c1(power)),
118 }
119 }
120
121 pub fn exp_by_neg_z(&self) -> Fq12 {
122 self.cyclotomic_pow(U256::from([4965661367192848881, 0, 0, 0]))
123 .unitary_inverse()
124 }
125
126 pub fn unitary_inverse(&self) -> Fq12 {
127 Fq12::new(self.c0, -self.c1)
128 }
129
130 pub fn mul_by_024(&self, ell_0: Fq2, ell_vw: Fq2, ell_vv: Fq2) -> Fq12 {
131 let z0 = self.c0.c0;
132 let z1 = self.c0.c1;
133 let z2 = self.c0.c2;
134 let z3 = self.c1.c0;
135 let z4 = self.c1.c1;
136 let z5 = self.c1.c2;
137
138 let x0 = ell_0;
139 let x2 = ell_vv;
140 let x4 = ell_vw;
141
142 let d0 = z0 * x0;
143 let d2 = z2 * x2;
144 let d4 = z4 * x4;
145 let t2 = z0 + z4;
146 let t1 = z0 + z2;
147 let s0 = z1 + z3 + z5;
148
149 let s1 = z1 * x2;
150 let t3 = s1 + d4;
151 let t4 = t3.mul_by_nonresidue() + d0;
152 let z0 = t4;
153
154 let t3 = z5 * x4;
155 let s1 = s1 + t3;
156 let t3 = t3 + d2;
157 let t4 = t3.mul_by_nonresidue();
158 let t3 = z1 * x0;
159 let s1 = s1 + t3;
160 let t4 = t4 + t3;
161 let z1 = t4;
162
163 let t0 = x0 + x2;
164 let t3 = t1 * t0 - d0 - d2;
165 let t4 = z3 * x4;
166 let s1 = s1 + t4;
167 let t3 = t3 + t4;
168
169 let t0 = z2 + z4;
170 let z2 = t3;
171
172 let t1 = x2 + x4;
173 let t3 = t0 * t1 - d2 - d4;
174 let t4 = t3.mul_by_nonresidue();
175 let t3 = z3 * x0;
176 let s1 = s1 + t3;
177 let t4 = t4 + t3;
178 let z3 = t4;
179
180 let t3 = z5 * x2;
181 let s1 = s1 + t3;
182 let t4 = t3.mul_by_nonresidue();
183 let t0 = x0 + x4;
184 let t3 = t2 * t0 - d0 - d4;
185 let t4 = t4 + t3;
186 let z4 = t4;
187
188 let t0 = x0 + x2 + x4;
189 let t3 = s0 * t0 - s1;
190 let z5 = t3;
191
192 Fq12 {
193 c0: Fq6::new(z0, z1, z2),
194 c1: Fq6::new(z3, z4, z5),
195 }
196 }
197
198 pub fn cyclotomic_squared(&self) -> Self {
199 let z0 = self.c0.c0;
200 let z4 = self.c0.c1;
201 let z3 = self.c0.c2;
202 let z2 = self.c1.c0;
203 let z1 = self.c1.c1;
204 let z5 = self.c1.c2;
205
206 let tmp = z0 * z1;
207 let t0 = (z0 + z1) * (z1.mul_by_nonresidue() + z0) - tmp - tmp.mul_by_nonresidue();
208 let t1 = tmp + tmp;
209
210 let tmp = z2 * z3;
211 let t2 = (z2 + z3) * (z3.mul_by_nonresidue() + z2) - tmp - tmp.mul_by_nonresidue();
212 let t3 = tmp + tmp;
213
214 let tmp = z4 * z5;
215 let t4 = (z4 + z5) * (z5.mul_by_nonresidue() + z4) - tmp - tmp.mul_by_nonresidue();
216 let t5 = tmp + tmp;
217
218 let z0 = t0 - z0;
219 let z0 = z0 + z0;
220 let z0 = z0 + t0;
221
222 let z1 = t1 + z1;
223 let z1 = z1 + z1;
224 let z1 = z1 + t1;
225
226 let tmp = t5.mul_by_nonresidue();
227 let z2 = tmp + z2;
228 let z2 = z2 + z2;
229 let z2 = z2 + tmp;
230
231 let z3 = t4 - z3;
232 let z3 = z3 + z3;
233 let z3 = z3 + t4;
234
235 let z4 = t2 - z4;
236 let z4 = z4 + z4;
237 let z4 = z4 + t2;
238
239 let z5 = t3 + z5;
240 let z5 = z5 + z5;
241 let z5 = z5 + t3;
242
243 Fq12 {
244 c0: Fq6::new(z0, z4, z3),
245 c1: Fq6::new(z2, z1, z5),
246 }
247 }
248
249 pub fn cyclotomic_pow<I: Into<U256>>(&self, by: I) -> Self {
250 let mut res = Self::one();
251
252 let mut found_one = false;
253
254 for i in by.into().bits() {
255 if found_one {
256 res = res.cyclotomic_squared();
257 }
258
259 if i {
260 found_one = true;
261 res = *self * res;
262 }
263 }
264
265 res
266 }
267}
268
269impl FieldElement for Fq12 {
270 fn zero() -> Self {
271 Fq12 {
272 c0: Fq6::zero(),
273 c1: Fq6::zero(),
274 }
275 }
276
277 fn one() -> Self {
278 Fq12 {
279 c0: Fq6::one(),
280 c1: Fq6::zero(),
281 }
282 }
283
284 fn random<R: Rng>(rng: &mut R) -> Self {
285 Fq12 {
286 c0: Fq6::random(rng),
287 c1: Fq6::random(rng),
288 }
289 }
290
291 fn is_zero(&self) -> bool {
292 self.c0.is_zero() && self.c1.is_zero()
293 }
294
295 fn squared(&self) -> Self {
296 let ab = self.c0 * self.c1;
297
298 Fq12 {
299 c0: (self.c1.mul_by_nonresidue() + self.c0) * (self.c0 + self.c1) - ab
300 - ab.mul_by_nonresidue(),
301 c1: ab + ab,
302 }
303 }
304
305 fn inverse(self) -> Option<Self> {
306 match (self.c0.squared() - (self.c1.squared().mul_by_nonresidue())).inverse() {
307 Some(t) => Some(Fq12 {
308 c0: self.c0 * t,
309 c1: -(self.c1 * t),
310 }),
311 None => None,
312 }
313 }
314}
315
316impl Mul for Fq12 {
317 type Output = Fq12;
318
319 fn mul(self, other: Fq12) -> Fq12 {
320 let aa = self.c0 * other.c0;
321 let bb = self.c1 * other.c1;
322
323 Fq12 {
324 c0: bb.mul_by_nonresidue() + aa,
325 c1: (self.c0 + self.c1) * (other.c0 + other.c1) - aa - bb,
326 }
327 }
328}
329
330impl Sub for Fq12 {
331 type Output = Fq12;
332
333 fn sub(self, other: Fq12) -> Fq12 {
334 Fq12 {
335 c0: self.c0 - other.c0,
336 c1: self.c1 - other.c1,
337 }
338 }
339}
340
341impl Add for Fq12 {
342 type Output = Fq12;
343
344 fn add(self, other: Fq12) -> Fq12 {
345 Fq12 {
346 c0: self.c0 + other.c0,
347 c1: self.c1 + other.c1,
348 }
349 }
350}
351
352impl Neg for Fq12 {
353 type Output = Fq12;
354
355 fn neg(self) -> Fq12 {
356 Fq12 {
357 c0: -self.c0,
358 c1: -self.c1,
359 }
360 }
361}