halo2curves_axiom/bls12_381/
fp6.rs

Help
1//! Source: <https://github.com/privacy-scaling-explorations/bls12_381>
2
3use super::fp::*;
4use super::fp2::*;
5
6use core::fmt;
7use core::ops::{Add, Mul, Neg, Sub};
8use subtle::{Choice, ConditionallySelectable, ConstantTimeEq, CtOption};
9
10use rand_core::RngCore;
11
12use crate::{
13    impl_add_binop_specify_output, impl_binops_additive, impl_binops_additive_specify_output,
14    impl_binops_multiplicative, impl_binops_multiplicative_mixed, impl_sub_binop_specify_output,
15};
16
17/// This represents an element $c_0 + c_1 v + c_2 v^2$ of $\mathbb{F}_{p^6} = \mathbb{F}_{p^2}\[v\] / (v^3 - u - 1)$.
18pub struct Fp6 {
19    pub c0: Fp2,
20    pub c1: Fp2,
21    pub c2: Fp2,
22}
23
24impl From<Fp> for Fp6 {
25    fn from(f: Fp) -> Fp6 {
26        Fp6 {
27            c0: Fp2::from(f),
28            c1: Fp2::zero(),
29            c2: Fp2::zero(),
30        }
31    }
32}
33
34impl From<Fp2> for Fp6 {
35    fn from(f: Fp2) -> Fp6 {
36        Fp6 {
37            c0: f,
38            c1: Fp2::zero(),
39            c2: Fp2::zero(),
40        }
41    }
42}
43
44impl Eq for Fp6 {}
45impl PartialEq for Fp6 {
46    fn eq(&self, other: &Fp6) -> bool {
47        self.ct_eq(other).into()
48    }
49}
50
51impl Copy for Fp6 {}
52impl Clone for Fp6 {
53    #[inline]
54    fn clone(&self) -> Self {
55        *self
56    }
57}
58
59impl Default for Fp6 {
60    fn default() -> Self {
61        Fp6::zero()
62    }
63}
64
65#[cfg(feature = "zeroize")]
66impl zeroize::DefaultIsZeroes for Fp6 {}
67
68impl fmt::Debug for Fp6 {
69    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
70        write!(f, "{:?} + ({:?})*v + ({:?})*v^2", self.c0, self.c1, self.c2)
71    }
72}
73
74impl ConditionallySelectable for Fp6 {
75    #[inline(always)]
76    fn conditional_select(a: &Self, b: &Self, choice: Choice) -> Self {
77        Fp6 {
78            c0: Fp2::conditional_select(&a.c0, &b.c0, choice),
79            c1: Fp2::conditional_select(&a.c1, &b.c1, choice),
80            c2: Fp2::conditional_select(&a.c2, &b.c2, choice),
81        }
82    }
83}
84
85impl ConstantTimeEq for Fp6 {
86    #[inline(always)]
87    fn ct_eq(&self, other: &Self) -> Choice {
88        self.c0.ct_eq(&other.c0) & self.c1.ct_eq(&other.c1) & self.c2.ct_eq(&other.c2)
89    }
90}
91
92impl Fp6 {
93    #[inline]
94    pub const fn zero() -> Self {
95        Fp6 {
96            c0: Fp2::zero(),
97            c1: Fp2::zero(),
98            c2: Fp2::zero(),
99        }
100    }
101
102    #[inline]
103    pub const fn one() -> Self {
104        Fp6 {
105            c0: Fp2::one(),
106            c1: Fp2::zero(),
107            c2: Fp2::zero(),
108        }
109    }
110
111    pub(crate) fn random(mut rng: impl RngCore) -> Self {
112        Fp6 {
113            c0: Fp2::random(&mut rng),
114            c1: Fp2::random(&mut rng),
115            c2: Fp2::random(&mut rng),
116        }
117    }
118
119    pub fn double(&self) -> Self {
120        Self {
121            c0: self.c0.double(),
122            c1: self.c1.double(),
123            c2: self.c2.double(),
124        }
125    }
126
127    pub fn mul_by_1(&self, c1: &Fp2) -> Fp6 {
128        Fp6 {
129            c0: (self.c2 * c1).mul_by_nonresidue(),
130            c1: self.c0 * c1,
131            c2: self.c1 * c1,
132        }
133    }
134
135    pub fn mul_by_01(&self, c0: &Fp2, c1: &Fp2) -> Fp6 {
136        let a_a = self.c0 * c0;
137        let b_b = self.c1 * c1;
138
139        let t1 = (self.c2 * c1).mul_by_nonresidue() + a_a;
140
141        let t2 = (c0 + c1) * (self.c0 + self.c1) - a_a - b_b;
142
143        let t3 = self.c2 * c0 + b_b;
144
145        Fp6 {
146            c0: t1,
147            c1: t2,
148            c2: t3,
149        }
150    }
151
152    /// Multiply by quadratic nonresidue v.
153    pub fn mul_by_nonresidue(&self) -> Self {
154        // Given a + bv + cv^2, this produces
155        //     av + bv^2 + cv^3
156        // but because v^3 = u + 1, we have
157        //     c(u + 1) + av + v^2
158
159        Fp6 {
160            c0: self.c2.mul_by_nonresidue(),
161            c1: self.c0,
162            c2: self.c1,
163        }
164    }
165
166    /// Raises this element to p.
167    #[inline(always)]
168    pub fn frobenius_map(&self) -> Self {
169        let c0 = self.c0.frobenius_map();
170        let c1 = self.c1.frobenius_map();
171        let c2 = self.c2.frobenius_map();
172
173        // c1 = c1 * (u + 1)^((p - 1) / 3)
174        let c1 = c1
175            * Fp2 {
176                c0: Fp::zero(),
177                c1: Fp::from_raw_unchecked([
178                    0xcd03_c9e4_8671_f071,
179                    0x5dab_2246_1fcd_a5d2,
180                    0x5870_42af_d385_1b95,
181                    0x8eb6_0ebe_01ba_cb9e,
182                    0x03f9_7d6e_83d0_50d2,
183                    0x18f0_2065_5463_8741,
184                ]),
185            };
186
187        // c2 = c2 * (u + 1)^((2p - 2) / 3)
188        let c2 = c2
189            * Fp2 {
190                c0: Fp::from_raw_unchecked([
191                    0x890d_c9e4_8675_45c3,
192                    0x2af3_2253_3285_a5d5,
193                    0x5088_0866_309b_7e2c,
194                    0xa20d_1b8c_7e88_1024,
195                    0x14e4_f04f_e2db_9068,
196                    0x14e5_6d3f_1564_853a,
197                ]),
198                c1: Fp::zero(),
199            };
200
201        Fp6 { c0, c1, c2 }
202    }
203
204    #[inline(always)]
205    pub fn is_zero(&self) -> Choice {
206        self.c0.is_zero() & self.c1.is_zero() & self.c2.is_zero()
207    }
208
209    /// Returns `c = self * b`.
210    ///
211    /// Implements the full-tower interleaving strategy from
212    /// [ePrint 2022-376](https://eprint.iacr.org/2022/367).
213    #[inline]
214    fn mul_interleaved(&self, b: &Self) -> Self {
215        // The intuition for this algorithm is that we can look at F_p^6 as a direct
216        // extension of F_p^2, and express the overall operations down to the base field
217        // F_p instead of only over F_p^2. This enables us to interleave multiplications
218        // and reductions, ensuring that we don't require double-width intermediate
219        // representations (with around twice as many limbs as F_p elements).
220
221        // We want to express the multiplication c = a x b, where a = (a_0, a_1, a_2) is
222        // an element of F_p^6, and a_i = (a_i,0, a_i,1) is an element of F_p^2. The fully
223        // expanded multiplication is given by (2022-376 §5):
224        //
225        //   c_0,0 = a_0,0 b_0,0 - a_0,1 b_0,1 + a_1,0 b_2,0 - a_1,1 b_2,1 + a_2,0 b_1,0 - a_2,1 b_1,1
226        //                                     - a_1,0 b_2,1 - a_1,1 b_2,0 - a_2,0 b_1,1 - a_2,1 b_1,0.
227        //         = a_0,0 b_0,0 - a_0,1 b_0,1 + a_1,0 (b_2,0 - b_2,1) - a_1,1 (b_2,0 + b_2,1)
228        //                                     + a_2,0 (b_1,0 - b_1,1) - a_2,1 (b_1,0 + b_1,1).
229        //
230        //   c_0,1 = a_0,0 b_0,1 + a_0,1 b_0,0 + a_1,0 b_2,1 + a_1,1 b_2,0 + a_2,0 b_1,1 + a_2,1 b_1,0
231        //                                     + a_1,0 b_2,0 - a_1,1 b_2,1 + a_2,0 b_1,0 - a_2,1 b_1,1.
232        //         = a_0,0 b_0,1 + a_0,1 b_0,0 + a_1,0(b_2,0 + b_2,1) + a_1,1(b_2,0 - b_2,1)
233        //                                     + a_2,0(b_1,0 + b_1,1) + a_2,1(b_1,0 - b_1,1).
234        //
235        //   c_1,0 = a_0,0 b_1,0 - a_0,1 b_1,1 + a_1,0 b_0,0 - a_1,1 b_0,1 + a_2,0 b_2,0 - a_2,1 b_2,1
236        //                                                                 - a_2,0 b_2,1 - a_2,1 b_2,0.
237        //         = a_0,0 b_1,0 - a_0,1 b_1,1 + a_1,0 b_0,0 - a_1,1 b_0,1 + a_2,0(b_2,0 - b_2,1)
238        //                                                                 - a_2,1(b_2,0 + b_2,1).
239        //
240        //   c_1,1 = a_0,0 b_1,1 + a_0,1 b_1,0 + a_1,0 b_0,1 + a_1,1 b_0,0 + a_2,0 b_2,1 + a_2,1 b_2,0
241        //                                                                 + a_2,0 b_2,0 - a_2,1 b_2,1
242        //         = a_0,0 b_1,1 + a_0,1 b_1,0 + a_1,0 b_0,1 + a_1,1 b_0,0 + a_2,0(b_2,0 + b_2,1)
243        //                                                                 + a_2,1(b_2,0 - b_2,1).
244        //
245        //   c_2,0 = a_0,0 b_2,0 - a_0,1 b_2,1 + a_1,0 b_1,0 - a_1,1 b_1,1 + a_2,0 b_0,0 - a_2,1 b_0,1.
246        //   c_2,1 = a_0,0 b_2,1 + a_0,1 b_2,0 + a_1,0 b_1,1 + a_1,1 b_1,0 + a_2,0 b_0,1 + a_2,1 b_0,0.
247        //
248        // Each of these is a "sum of products", which we can compute efficiently.
249
250        let a = self;
251        let b10_p_b11 = b.c1.c0 + b.c1.c1;
252        let b10_m_b11 = b.c1.c0 - b.c1.c1;
253        let b20_p_b21 = b.c2.c0 + b.c2.c1;
254        let b20_m_b21 = b.c2.c0 - b.c2.c1;
255
256        Fp6 {
257            c0: Fp2 {
258                c0: Fp::sum_of_products(
259                    [a.c0.c0, -a.c0.c1, a.c1.c0, -a.c1.c1, a.c2.c0, -a.c2.c1],
260                    [b.c0.c0, b.c0.c1, b20_m_b21, b20_p_b21, b10_m_b11, b10_p_b11],
261                ),
262                c1: Fp::sum_of_products(
263                    [a.c0.c0, a.c0.c1, a.c1.c0, a.c1.c1, a.c2.c0, a.c2.c1],
264                    [b.c0.c1, b.c0.c0, b20_p_b21, b20_m_b21, b10_p_b11, b10_m_b11],
265                ),
266            },
267            c1: Fp2 {
268                c0: Fp::sum_of_products(
269                    [a.c0.c0, -a.c0.c1, a.c1.c0, -a.c1.c1, a.c2.c0, -a.c2.c1],
270                    [b.c1.c0, b.c1.c1, b.c0.c0, b.c0.c1, b20_m_b21, b20_p_b21],
271                ),
272                c1: Fp::sum_of_products(
273                    [a.c0.c0, a.c0.c1, a.c1.c0, a.c1.c1, a.c2.c0, a.c2.c1],
274                    [b.c1.c1, b.c1.c0, b.c0.c1, b.c0.c0, b20_p_b21, b20_m_b21],
275                ),
276            },
277            c2: Fp2 {
278                c0: Fp::sum_of_products(
279                    [a.c0.c0, -a.c0.c1, a.c1.c0, -a.c1.c1, a.c2.c0, -a.c2.c1],
280                    [b.c2.c0, b.c2.c1, b.c1.c0, b.c1.c1, b.c0.c0, b.c0.c1],
281                ),
282                c1: Fp::sum_of_products(
283                    [a.c0.c0, a.c0.c1, a.c1.c0, a.c1.c1, a.c2.c0, a.c2.c1],
284                    [b.c2.c1, b.c2.c0, b.c1.c1, b.c1.c0, b.c0.c1, b.c0.c0],
285                ),
286            },
287        }
288    }
289
290    #[inline]
291    pub fn square(&self) -> Self {
292        let s0 = self.c0.square();
293        let ab = self.c0 * self.c1;
294        let s1 = ab + ab;
295        let s2 = (self.c0 - self.c1 + self.c2).square();
296        let bc = self.c1 * self.c2;
297        let s3 = bc + bc;
298        let s4 = self.c2.square();
299
300        Fp6 {
301            c0: s3.mul_by_nonresidue() + s0,
302            c1: s4.mul_by_nonresidue() + s1,
303            c2: s1 + s2 + s3 - s0 - s4,
304        }
305    }
306
307    #[inline]
308    pub fn invert(&self) -> CtOption<Self> {
309        let c0 = (self.c1 * self.c2).mul_by_nonresidue();
310        let c0 = self.c0.square() - c0;
311
312        let c1 = self.c2.square().mul_by_nonresidue();
313        let c1 = c1 - (self.c0 * self.c1);
314
315        let c2 = self.c1.square();
316        let c2 = c2 - (self.c0 * self.c2);
317
318        let tmp = ((self.c1 * c2) + (self.c2 * c1)).mul_by_nonresidue();
319        let tmp = tmp + (self.c0 * c0);
320
321        tmp.invert().map(|t| Fp6 {
322            c0: t * c0,
323            c1: t * c1,
324            c2: t * c2,
325        })
326    }
327}
328
329impl<'a, 'b> Mul<&'b Fp6> for &'a Fp6 {
330    type Output = Fp6;
331
332    #[inline]
333    fn mul(self, other: &'b Fp6) -> Self::Output {
334        self.mul_interleaved(other)
335    }
336}
337
338impl<'a, 'b> Add<&'b Fp6> for &'a Fp6 {
339    type Output = Fp6;
340
341    #[inline]
342    fn add(self, rhs: &'b Fp6) -> Self::Output {
343        Fp6 {
344            c0: self.c0 + rhs.c0,
345            c1: self.c1 + rhs.c1,
346            c2: self.c2 + rhs.c2,
347        }
348    }
349}
350
351impl<'a> Neg for &'a Fp6 {
352    type Output = Fp6;
353
354    #[inline]
355    fn neg(self) -> Self::Output {
356        Fp6 {
357            c0: -self.c0,
358            c1: -self.c1,
359            c2: -self.c2,
360        }
361    }
362}
363
364impl Neg for Fp6 {
365    type Output = Fp6;
366
367    #[inline]
368    fn neg(self) -> Self::Output {
369        -&self
370    }
371}
372
373impl<'a, 'b> Sub<&'b Fp6> for &'a Fp6 {
374    type Output = Fp6;
375
376    #[inline]
377    fn sub(self, rhs: &'b Fp6) -> Self::Output {
378        Fp6 {
379            c0: self.c0 - rhs.c0,
380            c1: self.c1 - rhs.c1,
381            c2: self.c2 - rhs.c2,
382        }
383    }
384}
385
386impl_binops_additive!(Fp6, Fp6);
387impl_binops_multiplicative!(Fp6, Fp6);
388
389#[test]
390fn test_arithmetic() {
391    use super::fp::*;
392
393    let a = Fp6 {
394        c0: Fp2 {
395            c0: Fp::from_raw_unchecked([
396                0x47f9_cb98_b1b8_2d58,
397                0x5fe9_11eb_a3aa_1d9d,
398                0x96bf_1b5f_4dd8_1db3,
399                0x8100_d27c_c925_9f5b,
400                0xafa2_0b96_7464_0eab,
401                0x09bb_cea7_d8d9_497d,
402            ]),
403            c1: Fp::from_raw_unchecked([
404                0x0303_cb98_b166_2daa,
405                0xd931_10aa_0a62_1d5a,
406                0xbfa9_820c_5be4_a468,
407                0x0ba3_643e_cb05_a348,
408                0xdc35_34bb_1f1c_25a6,
409                0x06c3_05bb_19c0_e1c1,
410            ]),
411        },
412        c1: Fp2 {
413            c0: Fp::from_raw_unchecked([
414                0x46f9_cb98_b162_d858,
415                0x0be9_109c_f7aa_1d57,
416                0xc791_bc55_fece_41d2,
417                0xf84c_5770_4e38_5ec2,
418                0xcb49_c1d9_c010_e60f,
419                0x0acd_b8e1_58bf_e3c8,
420            ]),
421            c1: Fp::from_raw_unchecked([
422                0x8aef_cb98_b15f_8306,
423                0x3ea1_108f_e4f2_1d54,
424                0xcf79_f69f_a1b7_df3b,
425                0xe4f5_4aa1_d16b_1a3c,
426                0xba5e_4ef8_6105_a679,
427                0x0ed8_6c07_97be_e5cf,
428            ]),
429        },
430        c2: Fp2 {
431            c0: Fp::from_raw_unchecked([
432                0xcee5_cb98_b15c_2db4,
433                0x7159_1082_d23a_1d51,
434                0xd762_30e9_44a1_7ca4,
435                0xd19e_3dd3_549d_d5b6,
436                0xa972_dc17_01fa_66e3,
437                0x12e3_1f2d_d6bd_e7d6,
438            ]),
439            c1: Fp::from_raw_unchecked([
440                0xad2a_cb98_b173_2d9d,
441                0x2cfd_10dd_0696_1d64,
442                0x0739_6b86_c6ef_24e8,
443                0xbd76_e2fd_b1bf_c820,
444                0x6afe_a7f6_de94_d0d5,
445                0x1099_4b0c_5744_c040,
446            ]),
447        },
448    };
449
450    let b = Fp6 {
451        c0: Fp2 {
452            c0: Fp::from_raw_unchecked([
453                0xf120_cb98_b16f_d84b,
454                0x5fb5_10cf_f3de_1d61,
455                0x0f21_a5d0_69d8_c251,
456                0xaa1f_d62f_34f2_839a,
457                0x5a13_3515_7f89_913f,
458                0x14a3_fe32_9643_c247,
459            ]),
460            c1: Fp::from_raw_unchecked([
461                0x3516_cb98_b16c_82f9,
462                0x926d_10c2_e126_1d5f,
463                0x1709_e01a_0cc2_5fba,
464                0x96c8_c960_b825_3f14,
465                0x4927_c234_207e_51a9,
466                0x18ae_b158_d542_c44e,
467            ]),
468        },
469        c1: Fp2 {
470            c0: Fp::from_raw_unchecked([
471                0xbf0d_cb98_b169_82fc,
472                0xa679_10b7_1d1a_1d5c,
473                0xb7c1_47c2_b8fb_06ff,
474                0x1efa_710d_47d2_e7ce,
475                0xed20_a79c_7e27_653c,
476                0x02b8_5294_dac1_dfba,
477            ]),
478            c1: Fp::from_raw_unchecked([
479                0x9d52_cb98_b180_82e5,
480                0x621d_1111_5176_1d6f,
481                0xe798_8260_3b48_af43,
482                0x0ad3_1637_a4f4_da37,
483                0xaeac_737c_5ac1_cf2e,
484                0x006e_7e73_5b48_b824,
485            ]),
486        },
487        c2: Fp2 {
488            c0: Fp::from_raw_unchecked([
489                0xe148_cb98_b17d_2d93,
490                0x94d5_1104_3ebe_1d6c,
491                0xef80_bca9_de32_4cac,
492                0xf77c_0969_2827_95b1,
493                0x9dc1_009a_fbb6_8f97,
494                0x0479_3199_9a47_ba2b,
495            ]),
496            c1: Fp::from_raw_unchecked([
497                0x253e_cb98_b179_d841,
498                0xc78d_10f7_2c06_1d6a,
499                0xf768_f6f3_811b_ea15,
500                0xe424_fc9a_ab5a_512b,
501                0x8cd5_8db9_9cab_5001,
502                0x0883_e4bf_d946_bc32,
503            ]),
504        },
505    };
506
507    let c = Fp6 {
508        c0: Fp2 {
509            c0: Fp::from_raw_unchecked([
510                0x6934_cb98_b176_82ef,
511                0xfa45_10ea_194e_1d67,
512                0xff51_313d_2405_877e,
513                0xd0cd_efcc_2e8d_0ca5,
514                0x7bea_1ad8_3da0_106b,
515                0x0c8e_97e6_1845_be39,
516            ]),
517            c1: Fp::from_raw_unchecked([
518                0x4779_cb98_b18d_82d8,
519                0xb5e9_1144_4daa_1d7a,
520                0x2f28_6bda_a653_2fc2,
521                0xbca6_94f6_8bae_ff0f,
522                0x3d75_e6b8_1a3a_7a5d,
523                0x0a44_c3c4_98cc_96a3,
524            ]),
525        },
526        c1: Fp2 {
527            c0: Fp::from_raw_unchecked([
528                0x8b6f_cb98_b18a_2d86,
529                0xe8a1_1137_3af2_1d77,
530                0x3710_a624_493c_cd2b,
531                0xa94f_8828_0ee1_ba89,
532                0x2c8a_73d6_bb2f_3ac7,
533                0x0e4f_76ea_d7cb_98aa,
534            ]),
535            c1: Fp::from_raw_unchecked([
536                0xcf65_cb98_b186_d834,
537                0x1b59_112a_283a_1d74,
538                0x3ef8_e06d_ec26_6a95,
539                0x95f8_7b59_9214_7603,
540                0x1b9f_00f5_5c23_fb31,
541                0x125a_2a11_16ca_9ab1,
542            ]),
543        },
544        c2: Fp2 {
545            c0: Fp::from_raw_unchecked([
546                0x135b_cb98_b183_82e2,
547                0x4e11_111d_1582_1d72,
548                0x46e1_1ab7_8f10_07fe,
549                0x82a1_6e8b_1547_317d,
550                0x0ab3_8e13_fd18_bb9b,
551                0x1664_dd37_55c9_9cb8,
552            ]),
553            c1: Fp::from_raw_unchecked([
554                0xce65_cb98_b131_8334,
555                0xc759_0fdb_7c3a_1d2e,
556                0x6fcb_8164_9d1c_8eb3,
557                0x0d44_004d_1727_356a,
558                0x3746_b738_a7d0_d296,
559                0x136c_144a_96b1_34fc,
560            ]),
561        },
562    };
563
564    assert_eq!(a.square(), a * a);
565    assert_eq!(b.square(), b * b);
566    assert_eq!(c.square(), c * c);
567
568    assert_eq!((a + b) * c.square(), (c * c * a) + (c * c * b));
569
570    assert_eq!(
571        a.invert().unwrap() * b.invert().unwrap(),
572        (a * b).invert().unwrap()
573    );
574    assert_eq!(a.invert().unwrap() * a, Fp6::one());
575}
576
577#[cfg(feature = "zeroize")]
578#[test]
579fn test_zeroize() {
580    use zeroize::Zeroize;
581
582    let mut a = Fp6::one();
583    a.zeroize();
584    assert!(bool::from(a.is_zero()));
585}
halo2curves_axiom/bls12_381/fp6.rs

halo2curves_axiom/bls12_381/
fp6.rs
