ark_ff/fields/models/
fp2.rs

1use super::quadratic_extension::{QuadExtConfig, QuadExtField};
2use crate::{fields::PrimeField, CyclotomicMultSubgroup, Zero};
3use core::{marker::PhantomData, ops::Not};
4
5/// Trait that specifies constants and methods for defining degree-two extension fields.
6pub trait Fp2Config: 'static + Send + Sync + Sized {
7    /// Base prime field underlying this extension.
8    type Fp: PrimeField;
9
10    /// Quadratic non-residue in [`Self::Fp`] used to construct the extension
11    /// field. That is, `NONRESIDUE` is such that the quadratic polynomial
12    /// `f(X) = X^2 - Self::NONRESIDUE` in Fp\[X\] is irreducible in `Self::Fp`.
13    const NONRESIDUE: Self::Fp;
14
15    /// Coefficients for the Frobenius automorphism.
16    const FROBENIUS_COEFF_FP2_C1: &'static [Self::Fp];
17
18    /// Return `fe * Self::NONRESIDUE`.
19    /// Intended for specialization when [`Self::NONRESIDUE`] has a special
20    /// structure that can speed up multiplication
21    #[inline(always)]
22    fn mul_fp_by_nonresidue_in_place(fe: &mut Self::Fp) -> &mut Self::Fp {
23        *fe *= Self::NONRESIDUE;
24        fe
25    }
26
27    /// A specializable method for setting `y = x + NONRESIDUE * y`.
28    /// This allows for optimizations when the non-residue is
29    /// canonically negative in the field.
30    #[inline(always)]
31    fn mul_fp_by_nonresidue_and_add(y: &mut Self::Fp, x: &Self::Fp) {
32        Self::mul_fp_by_nonresidue_in_place(y);
33        *y += x;
34    }
35
36    /// A specializable method for computing x + mul_fp_by_nonresidue(y) + y
37    /// This allows for optimizations when the non-residue is not -1.
38    #[inline(always)]
39    fn mul_fp_by_nonresidue_plus_one_and_add(y: &mut Self::Fp, x: &Self::Fp) {
40        let old_y = *y;
41        Self::mul_fp_by_nonresidue_and_add(y, x);
42        *y += old_y;
43    }
44
45    /// A specializable method for computing x - mul_fp_by_nonresidue(y)
46    /// This allows for optimizations when the non-residue is
47    /// canonically negative in the field.
48    #[inline(always)]
49    fn sub_and_mul_fp_by_nonresidue(y: &mut Self::Fp, x: &Self::Fp) {
50        *y = *x - Self::mul_fp_by_nonresidue_in_place(y);
51    }
52}
53
54/// Wrapper for [`Fp2Config`], allowing combination of the [`Fp2Config`] and [`QuadExtConfig`] traits.
55pub struct Fp2ConfigWrapper<P: Fp2Config>(PhantomData<P>);
56
57impl<P: Fp2Config> QuadExtConfig for Fp2ConfigWrapper<P> {
58    type BasePrimeField = P::Fp;
59    type BaseField = P::Fp;
60    type FrobCoeff = P::Fp;
61
62    const DEGREE_OVER_BASE_PRIME_FIELD: usize = 2;
63
64    const NONRESIDUE: Self::BaseField = P::NONRESIDUE;
65
66    const FROBENIUS_COEFF_C1: &'static [Self::FrobCoeff] = P::FROBENIUS_COEFF_FP2_C1;
67
68    #[inline(always)]
69    fn mul_base_field_by_nonresidue_in_place(fe: &mut Self::BaseField) -> &mut Self::BaseField {
70        P::mul_fp_by_nonresidue_in_place(fe)
71    }
72
73    #[inline(always)]
74    fn mul_base_field_by_nonresidue_and_add(y: &mut Self::BaseField, x: &Self::BaseField) {
75        P::mul_fp_by_nonresidue_and_add(y, x)
76    }
77
78    #[inline(always)]
79    fn mul_base_field_by_nonresidue_plus_one_and_add(y: &mut Self::BaseField, x: &Self::BaseField) {
80        P::mul_fp_by_nonresidue_plus_one_and_add(y, x)
81    }
82
83    #[inline(always)]
84    fn sub_and_mul_base_field_by_nonresidue(y: &mut Self::BaseField, x: &Self::BaseField) {
85        P::sub_and_mul_fp_by_nonresidue(y, x)
86    }
87
88    fn mul_base_field_by_frob_coeff(fe: &mut Self::BaseField, power: usize) {
89        *fe *= &Self::FROBENIUS_COEFF_C1[power % Self::DEGREE_OVER_BASE_PRIME_FIELD];
90    }
91}
92
93/// Alias for instances of quadratic extension fields. Helpful for omitting verbose
94/// instantiations involving `Fp2ConfigWrapper`.
95pub type Fp2<P> = QuadExtField<Fp2ConfigWrapper<P>>;
96
97impl<P: Fp2Config> Fp2<P> {
98    /// In-place multiply both coefficients `c0` and `c1` of `self`
99    /// by an element from [`Fp`](`Fp2Config::Fp`).
100    ///
101    /// # Examples
102    ///
103    /// ```
104    /// # use ark_std::test_rng;
105    /// # use ark_test_curves::bls12_381::{Fq as Fp, Fq2 as Fp2};
106    /// # use ark_std::UniformRand;
107    /// let c0: Fp = Fp::rand(&mut test_rng());
108    /// let c1: Fp = Fp::rand(&mut test_rng());
109    /// let mut ext_element: Fp2 = Fp2::new(c0, c1);
110    ///
111    /// let base_field_element: Fp = Fp::rand(&mut test_rng());
112    /// ext_element.mul_assign_by_fp(&base_field_element);
113    ///
114    /// assert_eq!(ext_element.c0, c0 * base_field_element);
115    /// assert_eq!(ext_element.c1, c1 * base_field_element);
116    /// ```
117    pub fn mul_assign_by_fp(&mut self, other: &P::Fp) {
118        self.c0 *= other;
119        self.c1 *= other;
120    }
121}
122
123impl<P: Fp2Config> CyclotomicMultSubgroup for Fp2<P> {
124    const INVERSE_IS_FAST: bool = true;
125    fn cyclotomic_inverse_in_place(&mut self) -> Option<&mut Self> {
126        // As the multiplicative subgroup is of order p^2 - 1, the
127        // only non-trivial cyclotomic subgroup is of order p+1
128        // Therefore, for any element in the cyclotomic subgroup, we have that `x^(p+1) = 1`.
129        // Recall that `x^(p+1)` in a quadratic extension field is equal
130        // to the norm in the base field, so we have that
131        // `x * x.conjugate() = 1`. By uniqueness of inverses,
132        // for this subgroup, x.inverse() = x.conjugate()
133
134        self.is_zero().not().then(|| {
135            self.conjugate_in_place();
136            self
137        })
138    }
139}
ark_ff/fields/models/fp2.rs

ark_ff/fields/models/
fp2.rs
