ark_ff/fields/models/
fp2.rs

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

ark_ff/fields/models/
fp2.rs
