halo2curves/bn256/
fq2.rs

1use core::convert::TryInto;
2use std::cmp::Ordering;
3
4use subtle::{Choice, CtOption};
5
6use super::fq::Fq;
7use crate::{
8    ff::{Field, FromUniformBytes, PrimeField, WithSmallOrderMulGroup},
9    ff_ext::{
10        quadratic::{QuadExtField, QuadExtFieldArith, SQRT},
11        ExtField, Legendre,
12    },
13};
14
15crate::impl_binops_additive!(Fq2, Fq2);
16crate::impl_binops_multiplicative!(Fq2, Fq2);
17crate::impl_binops_calls!(Fq2);
18crate::impl_sum_prod!(Fq2);
19crate::impl_tower2!(Fq, Fq2);
20crate::impl_tower2_from_uniform_bytes!(Fq, Fq2, 96);
21
22pub type Fq2 = QuadExtField<Fq>;
23impl QuadExtFieldArith for Fq2 {
24    type Base = Fq;
25    const SQRT: SQRT<Fq> = SQRT::Algorithm9 {
26        q_minus_3_over_4: &[
27            0x4f082305b61f3f51,
28            0x65e05aa45a1c72a3,
29            0x6e14116da0605617,
30            0x0c19139cb84c680a,
31        ],
32        q_minus_1_over_2: &[
33            0x9e10460b6c3e7ea3,
34            0xcbc0b548b438e546,
35            0xdc2822db40c0ac2e,
36            0x183227397098d014,
37        ],
38    };
39
40    fn square_assign(el: &mut QuadExtField<Self::Base>) {
41        let a = el.c0 + el.c1;
42        let b = el.c0 - el.c1;
43        let c = el.c0.double();
44        el.c0 = a * b;
45        el.c1 = c * el.c1;
46    }
47}
48
49impl ExtField for Fq2 {
50    const NON_RESIDUE: Self = Fq2::new(Fq::from_raw([9u64, 0, 0, 0]), Fq::ONE);
51
52    fn mul_by_nonresidue(&self) -> Self {
53        // (xu+y)(u+9) = (9x+y)u+(9y-x)
54        let t0 = self.c0;
55        let t1 = self.c1;
56        // 8*x*i + 8*y
57        let t = self.double().double().double();
58        Self {
59            // 9*y
60            c0: t.c0 + t0 - t1,
61            // (9*x + y)
62            c1: t.c1 + t0 + t1,
63        }
64    }
65
66    fn frobenius_map(&mut self, power: usize) {
67        if power % 2 != 0 {
68            self.conjugate();
69        }
70    }
71}
72
73#[cfg(test)]
74mod test {
75
76    use rand_core::RngCore;
77
78    use super::*;
79    use crate::{
80        arith_test, constants_test, f2_test, frobenius_test, legendre_test, serde_test, test,
81    };
82
83    constants_test!(Fq2);
84    arith_test!(Fq2);
85    legendre_test!(Fq2);
86    test!(arith, Fq2, sqrt_test, 1000);
87
88    serde_test!(Fq2);
89
90    f2_test!(Fq2, Fq);
91    frobenius_test!(Fq2, Fq, 20);
92
93    #[test]
94    fn test_fq2_mul_nonresidue() {
95        let e = Fq2::random(rand_core::OsRng);
96        let a0 = e.mul_by_nonresidue();
97        let a1 = e * Fq2::NON_RESIDUE;
98        assert_eq!(a0, a1);
99    }
100}