ark_ff/fields/models/
quadratic_extension.rs

1use crate::{
2    biginteger::BigInteger,
3    fields::{Field, LegendreSymbol, PrimeField},
4    AdditiveGroup, FftField, One, SqrtPrecomputation, ToConstraintField, UniformRand, Zero,
5};
6use ark_serialize::{
7    CanonicalDeserialize, CanonicalDeserializeWithFlags, CanonicalSerialize,
8    CanonicalSerializeWithFlags, Compress, EmptyFlags, Flags, SerializationError,
9};
10use ark_std::{
11    cmp::*,
12    fmt,
13    io::{Read, Write},
14    iter::*,
15    ops::{Add, AddAssign, Div, DivAssign, Mul, MulAssign, Neg, Sub, SubAssign},
16    rand::{
17        distributions::{Distribution, Standard},
18        Rng,
19    },
20    vec::*,
21};
22use zeroize::Zeroize;
23
24/// Defines a Quadratic extension field from a quadratic non-residue.
25pub trait QuadExtConfig: 'static + Send + Sync + Sized {
26    /// The prime field that this quadratic extension is eventually an extension of.
27    type BasePrimeField: PrimeField;
28    /// The base field that this field is a quadratic extension of.
29    ///
30    /// Note: while for simple instances of quadratic extensions such as `Fp2`
31    /// we might see `BaseField == BasePrimeField`, it won't always hold true.
32    /// E.g. for an extension tower: `BasePrimeField == Fp`, but `BaseField == Fp3`.
33    type BaseField: Field<BasePrimeField = Self::BasePrimeField>;
34    /// The type of the coefficients for an efficient implementation of the
35    /// Frobenius endomorphism.
36    type FrobCoeff: Field;
37
38    /// The degree of the extension over the base prime field.
39    const DEGREE_OVER_BASE_PRIME_FIELD: usize;
40
41    /// The quadratic non-residue used to construct the extension.
42    const NONRESIDUE: Self::BaseField;
43
44    /// Coefficients for the Frobenius automorphism.
45    const FROBENIUS_COEFF_C1: &[Self::FrobCoeff];
46
47    /// A specializable method for multiplying an element of the base field by
48    /// the quadratic non-residue. This is used in Karatsuba multiplication
49    /// and in complex squaring.
50    #[inline(always)]
51    fn mul_base_field_by_nonresidue_in_place(fe: &mut Self::BaseField) -> &mut Self::BaseField {
52        *fe *= &Self::NONRESIDUE;
53        fe
54    }
55
56    /// A specializable method for setting `y = x + NONRESIDUE * y`.
57    /// This allows for optimizations when the non-residue is
58    /// canonically negative in the field.
59    #[inline(always)]
60    fn mul_base_field_by_nonresidue_and_add(y: &mut Self::BaseField, x: &Self::BaseField) {
61        Self::mul_base_field_by_nonresidue_in_place(y);
62        *y += x;
63    }
64
65    /// A specializable method for computing x + mul_base_field_by_nonresidue(y) + y
66    /// This allows for optimizations when the non-residue is not -1.
67    #[inline(always)]
68    fn mul_base_field_by_nonresidue_plus_one_and_add(y: &mut Self::BaseField, x: &Self::BaseField) {
69        let old_y = *y;
70        Self::mul_base_field_by_nonresidue_and_add(y, x);
71        *y += old_y;
72    }
73
74    /// A specializable method for computing x - mul_base_field_by_nonresidue(y)
75    /// This allows for optimizations when the non-residue is
76    /// canonically negative in the field.
77    #[inline(always)]
78    fn sub_and_mul_base_field_by_nonresidue(y: &mut Self::BaseField, x: &Self::BaseField) {
79        Self::mul_base_field_by_nonresidue_in_place(y);
80        let mut result = *x;
81        result -= &*y;
82        *y = result;
83    }
84
85    /// A specializable method for multiplying an element of the base field by
86    /// the appropriate Frobenius coefficient.
87    fn mul_base_field_by_frob_coeff(fe: &mut Self::BaseField, power: usize);
88}
89
90/// An element of a quadratic extension field F_p\[X\]/(X^2 - P::NONRESIDUE) is
91/// represented as c0 + c1 * X, for c0, c1 in `P::BaseField`.
92#[derive(educe::Educe, CanonicalDeserialize)]
93#[educe(Default, Hash, Clone, Copy, Debug, PartialEq, Eq)]
94pub struct QuadExtField<P: QuadExtConfig> {
95    /// Coefficient `c0` in the representation of the field element `c = c0 + c1 * X`
96    pub c0: P::BaseField,
97    /// Coefficient `c1` in the representation of the field element `c = c0 + c1 * X`
98    pub c1: P::BaseField,
99}
100
101impl<P: QuadExtConfig> QuadExtField<P> {
102    /// Create a new field element from coefficients `c0` and `c1`,
103    /// so that the result is of the form `c0 + c1 * X`.
104    ///
105    /// # Examples
106    ///
107    /// ```
108    /// # use ark_std::test_rng;
109    /// # use ark_test_curves::bls12_381::{Fq as Fp, Fq2 as Fp2};
110    /// # use ark_std::UniformRand;
111    /// let c0: Fp = Fp::rand(&mut test_rng());
112    /// let c1: Fp = Fp::rand(&mut test_rng());
113    /// // `Fp2` a degree-2 extension over `Fp`.
114    /// let c: Fp2 = Fp2::new(c0, c1);
115    /// ```
116    pub const fn new(c0: P::BaseField, c1: P::BaseField) -> Self {
117        Self { c0, c1 }
118    }
119
120    /// This is only to be used when the element is *known* to be in the
121    /// cyclotomic subgroup.
122    pub fn conjugate_in_place(&mut self) -> &mut Self {
123        self.c1 = -self.c1;
124        self
125    }
126
127    /// Norm of QuadExtField over `P::BaseField`:`Norm(a) = a * a.conjugate()`.
128    /// This simplifies to: `Norm(a) = a.x^2 - P::NON_RESIDUE * a.y^2`.
129    /// This is alternatively expressed as `Norm(a) = a^(1 + p)`.
130    ///
131    /// # Examples
132    /// ```
133    /// # use ark_std::test_rng;
134    /// # use ark_std::{UniformRand, Zero};
135    /// # use ark_test_curves::{Field, bls12_381::Fq2 as Fp2};
136    /// let c: Fp2 = Fp2::rand(&mut test_rng());
137    /// let norm = c.norm();
138    /// // We now compute the norm using the `a * a.conjugate()` approach.
139    /// // A Frobenius map sends an element of `Fp2` to one of its p_th powers:
140    /// // `a.frobenius_map_in_place(1) -> a^p` and `a^p` is also `a`'s Galois conjugate.
141    /// let mut c_conjugate = c;
142    /// c_conjugate.frobenius_map_in_place(1);
143    /// let norm2 = c * c_conjugate;
144    /// // Computing the norm of an `Fp2` element should result in an element
145    /// // in BaseField `Fp`, i.e. `c1 == 0`
146    /// assert!(norm2.c1.is_zero());
147    /// assert_eq!(norm, norm2.c0);
148    /// ```
149    pub fn norm(&self) -> P::BaseField {
150        // t1 = c0.square() - P::NON_RESIDUE * c1^2
151        let mut result = self.c1.square();
152        P::sub_and_mul_base_field_by_nonresidue(&mut result, &self.c0.square());
153        result
154    }
155
156    /// In-place multiply both coefficients `c0` & `c1` of the quadratic
157    /// extension field by an element from the base field.
158    pub fn mul_assign_by_basefield(&mut self, element: &P::BaseField) {
159        self.c0 *= element;
160        self.c1 *= element;
161    }
162}
163
164impl<P: QuadExtConfig> Zero for QuadExtField<P> {
165    fn zero() -> Self {
166        QuadExtField::new(P::BaseField::zero(), P::BaseField::zero())
167    }
168
169    fn is_zero(&self) -> bool {
170        self.c0.is_zero() && self.c1.is_zero()
171    }
172}
173
174impl<P: QuadExtConfig> One for QuadExtField<P> {
175    fn one() -> Self {
176        QuadExtField::new(P::BaseField::one(), P::BaseField::zero())
177    }
178
179    fn is_one(&self) -> bool {
180        self.c0.is_one() && self.c1.is_zero()
181    }
182}
183
184impl<P: QuadExtConfig> AdditiveGroup for QuadExtField<P> {
185    type Scalar = Self;
186
187    const ZERO: Self = Self::new(P::BaseField::ZERO, P::BaseField::ZERO);
188
189    fn double(&self) -> Self {
190        let mut result = *self;
191        result.double_in_place();
192        result
193    }
194
195    fn double_in_place(&mut self) -> &mut Self {
196        self.c0.double_in_place();
197        self.c1.double_in_place();
198        self
199    }
200
201    fn neg_in_place(&mut self) -> &mut Self {
202        self.c0.neg_in_place();
203        self.c1.neg_in_place();
204        self
205    }
206}
207
208impl<P: QuadExtConfig> Field for QuadExtField<P> {
209    type BasePrimeField = P::BasePrimeField;
210
211    const SQRT_PRECOMP: Option<SqrtPrecomputation<Self>> = None;
212
213    const ONE: Self = Self::new(P::BaseField::ONE, P::BaseField::ZERO);
214
215    const NEG_ONE: Self = Self::new(P::BaseField::NEG_ONE, P::BaseField::ZERO);
216
217    fn extension_degree() -> u64 {
218        2 * P::BaseField::extension_degree()
219    }
220
221    fn from_base_prime_field(elem: Self::BasePrimeField) -> Self {
222        let fe = P::BaseField::from_base_prime_field(elem);
223        Self::new(fe, P::BaseField::ZERO)
224    }
225
226    fn to_base_prime_field_elements(&self) -> impl Iterator<Item = Self::BasePrimeField> {
227        self.c0
228            .to_base_prime_field_elements()
229            .chain(self.c1.to_base_prime_field_elements())
230    }
231
232    fn from_base_prime_field_elems(
233        elems: impl IntoIterator<Item = Self::BasePrimeField>,
234    ) -> Option<Self> {
235        let mut iter = elems.into_iter();
236        let d = P::BaseField::extension_degree() as usize;
237
238        let a = P::BaseField::from_base_prime_field_elems(iter.by_ref().take(d))?;
239        let b = P::BaseField::from_base_prime_field_elems(iter.by_ref().take(d))?;
240
241        iter.next().is_none().then(|| Self::new(a, b))
242    }
243
244    fn square(&self) -> Self {
245        let mut result = *self;
246        result.square_in_place();
247        result
248    }
249
250    #[inline]
251    fn from_random_bytes_with_flags<F: Flags>(bytes: &[u8]) -> Option<(Self, F)> {
252        let split_at = bytes.len() / 2;
253        if let Some(c0) = P::BaseField::from_random_bytes(&bytes[..split_at]) {
254            if let Some((c1, flags)) =
255                P::BaseField::from_random_bytes_with_flags(&bytes[split_at..])
256            {
257                return Some((QuadExtField::new(c0, c1), flags));
258            }
259        }
260        None
261    }
262
263    #[inline]
264    fn from_random_bytes(bytes: &[u8]) -> Option<Self> {
265        Self::from_random_bytes_with_flags::<EmptyFlags>(bytes).map(|f| f.0)
266    }
267
268    fn square_in_place(&mut self) -> &mut Self {
269        // (c0, c1)^2 = (c0 + x*c1)^2
270        //            = c0^2 + 2 c0 c1 x + c1^2 x^2
271        //            = c0^2 + beta * c1^2 + 2 c0 * c1 * x
272        //            = (c0^2 + beta * c1^2, 2 c0 * c1)
273        // Where beta is P::NONRESIDUE.
274        // When beta = -1, we can re-use intermediate additions to improve performance.
275        if P::NONRESIDUE == P::BaseField::NEG_ONE {
276            // When the non-residue is -1, we save 2 intermediate additions,
277            // and use one fewer intermediate variable
278
279            let c0_copy = self.c0;
280            // v0 = c0 - c1
281            let mut v0 = self.c0;
282            v0 -= &self.c1;
283            self.c0 += self.c1;
284            // result.c0 *= (c0 - c1)
285            // result.c0 = (c0 - c1) * (c0 + c1) = c0^2 - c1^2
286            self.c0 *= &v0;
287
288            // result.c1 = 2 c1
289            self.c1.double_in_place();
290            // result.c1 *= c0
291            // result.c1 = (2 * c1) * c0
292            self.c1 *= &c0_copy;
293
294            self
295        } else {
296            // v0 = c0 - c1
297            let mut v0 = self.c0 - &self.c1;
298            // v3 = c0 - beta * c1
299            let mut v3 = self.c1;
300            P::sub_and_mul_base_field_by_nonresidue(&mut v3, &self.c0);
301            // v2 = c0 * c1
302            let v2 = self.c0 * &self.c1;
303
304            // v0 = (v0 * v3)
305            // v0 = (c0 - c1) * (c0 - beta*c1)
306            // v0 = c0^2 - beta * c0 * c1 - c0 * c1 + beta * c1^2
307            v0 *= &v3;
308
309            // result.c1 = 2 * c0 * c1
310            self.c1 = v2;
311            self.c1.double_in_place();
312            // result.c0 = (c0^2 - beta * c0 * c1 - c0 * c1 + beta * c1^2) + ((beta + 1) c0 * c1)
313            // result.c0 = (c0^2 - beta * c0 * c1 + beta * c1^2) + (beta * c0 * c1)
314            // result.c0 = c0^2 + beta * c1^2
315            self.c0 = v2;
316            P::mul_base_field_by_nonresidue_plus_one_and_add(&mut self.c0, &v0);
317
318            self
319        }
320    }
321
322    fn inverse(&self) -> Option<Self> {
323        if self.is_zero() {
324            None
325        } else {
326            // Guide to Pairing-based Cryptography, Algorithm 5.19.
327            // v1 = c1.square()
328            let v1 = self.c1.square();
329            // v0 = c0.square() - beta * v1
330            let mut v0 = v1;
331            P::sub_and_mul_base_field_by_nonresidue(&mut v0, &self.c0.square());
332
333            v0.inverse().map(|v1| {
334                let c0 = self.c0 * &v1;
335                let c1 = -(self.c1 * &v1);
336                Self::new(c0, c1)
337            })
338        }
339    }
340
341    fn inverse_in_place(&mut self) -> Option<&mut Self> {
342        self.inverse().map(|inverse| {
343            *self = inverse;
344            self
345        })
346    }
347
348    fn frobenius_map_in_place(&mut self, power: usize) {
349        self.c0.frobenius_map_in_place(power);
350        self.c1.frobenius_map_in_place(power);
351        P::mul_base_field_by_frob_coeff(&mut self.c1, power);
352    }
353
354    fn legendre(&self) -> LegendreSymbol {
355        // The LegendreSymbol in a field of order q for an element x can be
356        // computed as x^((q-1)/2).
357        // Since we are in a quadratic extension of a field F_p,
358        // we have that q = p^2.
359        // Notice then that (q-1)/2 = ((p-1)/2) * (1 + p).
360        // This implies that we can compute the symbol as (x^(1+p))^((p-1)/2).
361        // Recall that computing x^(1 + p) is equivalent to taking the norm of x,
362        // and it will output an element in the base field F_p.
363        // Then exponentiating by (p-1)/2 in the base field is equivalent to computing
364        // the legendre symbol in the base field.
365        self.norm().legendre()
366    }
367
368    fn sqrt(&self) -> Option<Self> {
369        // Square root based on the complex method. See
370        // https://eprint.iacr.org/2012/685.pdf (page 15, algorithm 8)
371        if self.c1.is_zero() {
372            // for c = c0 + c1 * x, we have c1 = 0
373            // sqrt(c) == sqrt(c0) is an element of Fp2, i.e. sqrt(c0) = a = a0 + a1 * x for some a0, a1 in Fp
374            // squaring both sides: c0 = a0^2 + a1^2 * x^2 + (2 * a0 * a1 * x) = a0^2 + (a1^2 * P::NONRESIDUE)
375            // since there are no `x` terms on LHS, a0 * a1 = 0
376            // so either a0 = sqrt(c0) or a1 = sqrt(c0/P::NONRESIDUE)
377            if self.c0.legendre().is_qr() {
378                // either c0 is a valid sqrt in the base field
379                return self.c0.sqrt().map(|c0| Self::new(c0, P::BaseField::ZERO));
380            } else {
381                // or we need to compute sqrt(c0/P::NONRESIDUE)
382                return (self.c0.div(P::NONRESIDUE))
383                    .sqrt()
384                    .map(|res| Self::new(P::BaseField::ZERO, res));
385            }
386        }
387        // Try computing the square root
388        // Check at the end of the algorithm if it was a square root
389        let alpha = self.norm();
390
391        // Compute `(p+1)/2` as `1/2`.
392        // This is cheaper than `P::BaseField::one().double().inverse()`
393        let mut two_inv = P::BasePrimeField::MODULUS;
394
395        two_inv.add_with_carry(&1u64.into());
396        two_inv.div2();
397
398        let two_inv = P::BasePrimeField::from(two_inv);
399        let two_inv = P::BaseField::from_base_prime_field(two_inv);
400
401        alpha.sqrt().and_then(|alpha| {
402            let mut delta = (alpha + &self.c0) * &two_inv;
403            if delta.legendre().is_qnr() {
404                delta -= &alpha;
405            }
406            let c0 = delta.sqrt().expect("Delta must have a square root");
407            let c0_inv = c0.inverse().expect("c0 must have an inverse");
408            let sqrt_cand = Self::new(c0, self.c1 * &two_inv * &c0_inv);
409            // Check if sqrt_cand is actually the square root
410            // if not, there exists no square root.
411            if sqrt_cand.square() == *self {
412                Some(sqrt_cand)
413            } else {
414                #[cfg(debug_assertions)]
415                {
416                    use crate::fields::LegendreSymbol::*;
417                    if self.legendre() != QuadraticNonResidue {
418                        panic!(
419                            "Input has a square root per its legendre symbol, but it was not found"
420                        )
421                    }
422                }
423                None
424            }
425        })
426    }
427
428    fn sqrt_in_place(&mut self) -> Option<&mut Self> {
429        (*self).sqrt().map(|sqrt| {
430            *self = sqrt;
431            self
432        })
433    }
434
435    fn mul_by_base_prime_field(&self, elem: &Self::BasePrimeField) -> Self {
436        let mut result = *self;
437        result.c0 = result.c0.mul_by_base_prime_field(elem);
438        result.c1 = result.c1.mul_by_base_prime_field(elem);
439        result
440    }
441}
442
443/// `QuadExtField` elements are ordered lexicographically.
444impl<P: QuadExtConfig> Ord for QuadExtField<P> {
445    #[inline(always)]
446    fn cmp(&self, other: &Self) -> Ordering {
447        match self.c1.cmp(&other.c1) {
448            Ordering::Greater => Ordering::Greater,
449            Ordering::Less => Ordering::Less,
450            Ordering::Equal => self.c0.cmp(&other.c0),
451        }
452    }
453}
454
455impl<P: QuadExtConfig> PartialOrd for QuadExtField<P> {
456    #[inline(always)]
457    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
458        Some(self.cmp(other))
459    }
460}
461
462impl<P: QuadExtConfig> Zeroize for QuadExtField<P> {
463    // The phantom data does not contain element-specific data
464    // and thus does not need to be zeroized.
465    fn zeroize(&mut self) {
466        self.c0.zeroize();
467        self.c1.zeroize();
468    }
469}
470
471impl<P: QuadExtConfig> From<u128> for QuadExtField<P> {
472    fn from(other: u128) -> Self {
473        Self::new(other.into(), P::BaseField::ZERO)
474    }
475}
476
477impl<P: QuadExtConfig> From<i128> for QuadExtField<P> {
478    #[inline]
479    fn from(val: i128) -> Self {
480        let abs = Self::from(val.unsigned_abs());
481        if val.is_positive() {
482            abs
483        } else {
484            -abs
485        }
486    }
487}
488
489impl<P: QuadExtConfig> From<u64> for QuadExtField<P> {
490    fn from(other: u64) -> Self {
491        Self::new(other.into(), P::BaseField::ZERO)
492    }
493}
494
495impl<P: QuadExtConfig> From<i64> for QuadExtField<P> {
496    #[inline]
497    fn from(val: i64) -> Self {
498        let abs = Self::from(val.unsigned_abs());
499        if val.is_positive() {
500            abs
501        } else {
502            -abs
503        }
504    }
505}
506
507impl<P: QuadExtConfig> From<u32> for QuadExtField<P> {
508    fn from(other: u32) -> Self {
509        Self::new(other.into(), P::BaseField::ZERO)
510    }
511}
512
513impl<P: QuadExtConfig> From<i32> for QuadExtField<P> {
514    #[inline]
515    fn from(val: i32) -> Self {
516        let abs = Self::from(val.unsigned_abs());
517        if val.is_positive() {
518            abs
519        } else {
520            -abs
521        }
522    }
523}
524
525impl<P: QuadExtConfig> From<u16> for QuadExtField<P> {
526    fn from(other: u16) -> Self {
527        Self::new(other.into(), P::BaseField::ZERO)
528    }
529}
530
531impl<P: QuadExtConfig> From<i16> for QuadExtField<P> {
532    #[inline]
533    fn from(val: i16) -> Self {
534        let abs = Self::from(val.unsigned_abs());
535        if val.is_positive() {
536            abs
537        } else {
538            -abs
539        }
540    }
541}
542
543impl<P: QuadExtConfig> From<u8> for QuadExtField<P> {
544    fn from(other: u8) -> Self {
545        Self::new(other.into(), P::BaseField::ZERO)
546    }
547}
548
549impl<P: QuadExtConfig> From<i8> for QuadExtField<P> {
550    #[inline]
551    fn from(val: i8) -> Self {
552        let abs = Self::from(val.unsigned_abs());
553        if val.is_positive() {
554            abs
555        } else {
556            -abs
557        }
558    }
559}
560
561impl<P: QuadExtConfig> From<bool> for QuadExtField<P> {
562    fn from(other: bool) -> Self {
563        Self::new(u8::from(other).into(), P::BaseField::ZERO)
564    }
565}
566
567impl<P: QuadExtConfig> Neg for QuadExtField<P> {
568    type Output = Self;
569    #[inline]
570    fn neg(mut self) -> Self {
571        self.c0.neg_in_place();
572        self.c1.neg_in_place();
573        self
574    }
575}
576
577impl<P: QuadExtConfig> Distribution<QuadExtField<P>> for Standard {
578    #[inline]
579    fn sample<R: Rng + ?Sized>(&self, rng: &mut R) -> QuadExtField<P> {
580        QuadExtField::new(UniformRand::rand(rng), UniformRand::rand(rng))
581    }
582}
583
584impl<P: QuadExtConfig> Add<&QuadExtField<P>> for QuadExtField<P> {
585    type Output = Self;
586
587    #[inline]
588    fn add(mut self, other: &Self) -> Self {
589        self += other;
590        self
591    }
592}
593
594impl<P: QuadExtConfig> Sub<&QuadExtField<P>> for QuadExtField<P> {
595    type Output = Self;
596
597    #[inline(always)]
598    fn sub(mut self, other: &Self) -> Self {
599        self -= other;
600        self
601    }
602}
603
604impl<P: QuadExtConfig> Mul<&QuadExtField<P>> for QuadExtField<P> {
605    type Output = Self;
606
607    #[inline(always)]
608    fn mul(mut self, other: &Self) -> Self {
609        self *= other;
610        self
611    }
612}
613
614impl<P: QuadExtConfig> Div<&QuadExtField<P>> for QuadExtField<P> {
615    type Output = Self;
616
617    #[inline]
618    #[allow(clippy::suspicious_arithmetic_impl)]
619    fn div(mut self, other: &Self) -> Self {
620        self *= &other.inverse().unwrap();
621        self
622    }
623}
624
625impl<P: QuadExtConfig> AddAssign<&Self> for QuadExtField<P> {
626    #[inline]
627    fn add_assign(&mut self, other: &Self) {
628        self.c0 += &other.c0;
629        self.c1 += &other.c1;
630    }
631}
632
633impl<P: QuadExtConfig> SubAssign<&Self> for QuadExtField<P> {
634    #[inline]
635    fn sub_assign(&mut self, other: &Self) {
636        self.c0 -= &other.c0;
637        self.c1 -= &other.c1;
638    }
639}
640
641impl_additive_ops_from_ref!(QuadExtField, QuadExtConfig);
642impl_multiplicative_ops_from_ref!(QuadExtField, QuadExtConfig);
643
644impl<P: QuadExtConfig> MulAssign<&Self> for QuadExtField<P> {
645    #[inline]
646    fn mul_assign(&mut self, other: &Self) {
647        if Self::extension_degree() == 2 {
648            let c1_input = [self.c0, self.c1];
649            P::mul_base_field_by_nonresidue_in_place(&mut self.c1);
650            *self = Self::new(
651                P::BaseField::sum_of_products(&[self.c0, self.c1], &[other.c0, other.c1]),
652                P::BaseField::sum_of_products(&c1_input, &[other.c1, other.c0]),
653            )
654        } else {
655            // Karatsuba multiplication;
656            // Guide to Pairing-based cryprography, Algorithm 5.16.
657            let mut v0 = self.c0;
658            v0 *= &other.c0;
659            let mut v1 = self.c1;
660            v1 *= &other.c1;
661
662            self.c1 += &self.c0;
663            self.c1 *= &(other.c0 + &other.c1);
664            self.c1 -= &v0;
665            self.c1 -= &v1;
666            self.c0 = v1;
667            P::mul_base_field_by_nonresidue_and_add(&mut self.c0, &v0);
668        }
669    }
670}
671
672impl<P: QuadExtConfig> DivAssign<&Self> for QuadExtField<P> {
673    #[inline]
674    fn div_assign(&mut self, other: &Self) {
675        *self *= &other.inverse().unwrap();
676    }
677}
678
679impl<P: QuadExtConfig> fmt::Display for QuadExtField<P> {
680    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
681        write!(f, "QuadExtField({} + {} * u)", self.c0, self.c1)
682    }
683}
684
685impl<P: QuadExtConfig> CanonicalSerializeWithFlags for QuadExtField<P> {
686    #[inline]
687    fn serialize_with_flags<W: Write, F: Flags>(
688        &self,
689        mut writer: W,
690        flags: F,
691    ) -> Result<(), SerializationError> {
692        self.c0.serialize_compressed(&mut writer)?;
693        self.c1.serialize_with_flags(&mut writer, flags)?;
694        Ok(())
695    }
696
697    #[inline]
698    fn serialized_size_with_flags<F: Flags>(&self) -> usize {
699        self.c0.compressed_size() + self.c1.serialized_size_with_flags::<F>()
700    }
701}
702
703impl<P: QuadExtConfig> CanonicalSerialize for QuadExtField<P> {
704    #[inline]
705    fn serialize_with_mode<W: Write>(
706        &self,
707        writer: W,
708        _compress: Compress,
709    ) -> Result<(), SerializationError> {
710        self.serialize_with_flags(writer, EmptyFlags)
711    }
712
713    #[inline]
714    fn serialized_size(&self, _compress: Compress) -> usize {
715        self.serialized_size_with_flags::<EmptyFlags>()
716    }
717}
718
719impl<P: QuadExtConfig> CanonicalDeserializeWithFlags for QuadExtField<P> {
720    #[inline]
721    fn deserialize_with_flags<R: Read, F: Flags>(
722        mut reader: R,
723    ) -> Result<(Self, F), SerializationError> {
724        let c0 = CanonicalDeserialize::deserialize_compressed(&mut reader)?;
725        let (c1, flags) = CanonicalDeserializeWithFlags::deserialize_with_flags(&mut reader)?;
726        Ok((QuadExtField::new(c0, c1), flags))
727    }
728}
729
730impl<P: QuadExtConfig> ToConstraintField<P::BasePrimeField> for QuadExtField<P>
731where
732    P::BaseField: ToConstraintField<P::BasePrimeField>,
733{
734    fn to_field_elements(&self) -> Option<Vec<P::BasePrimeField>> {
735        let mut res = Vec::new();
736        let mut c0_elems = self.c0.to_field_elements()?;
737        let mut c1_elems = self.c1.to_field_elements()?;
738
739        res.append(&mut c0_elems);
740        res.append(&mut c1_elems);
741
742        Some(res)
743    }
744}
745
746impl<P: QuadExtConfig> FftField for QuadExtField<P>
747where
748    P::BaseField: FftField,
749{
750    const GENERATOR: Self = Self::new(P::BaseField::GENERATOR, P::BaseField::ZERO);
751    const TWO_ADICITY: u32 = P::BaseField::TWO_ADICITY;
752    const TWO_ADIC_ROOT_OF_UNITY: Self =
753        Self::new(P::BaseField::TWO_ADIC_ROOT_OF_UNITY, P::BaseField::ZERO);
754    const SMALL_SUBGROUP_BASE: Option<u32> = P::BaseField::SMALL_SUBGROUP_BASE;
755    const SMALL_SUBGROUP_BASE_ADICITY: Option<u32> = P::BaseField::SMALL_SUBGROUP_BASE_ADICITY;
756    const LARGE_SUBGROUP_ROOT_OF_UNITY: Option<Self> =
757        if let Some(x) = P::BaseField::LARGE_SUBGROUP_ROOT_OF_UNITY {
758            Some(Self::new(x, P::BaseField::ZERO))
759        } else {
760            None
761        };
762}
763
764#[cfg(test)]
765mod quad_ext_tests {
766    use super::*;
767    use ark_std::test_rng;
768    use ark_test_curves::{
769        ark_ff::Field,
770        bls12_381::{Fq, Fq2},
771    };
772
773    #[test]
774    fn test_from_base_prime_field_elements() {
775        let ext_degree = Fq2::extension_degree() as usize;
776        // Test on slice lengths that aren't equal to the extension degree
777        let max_num_elems_to_test = 4;
778        for d in 0..max_num_elems_to_test {
779            if d == ext_degree {
780                continue;
781            }
782            let mut random_coeffs = Vec::new();
783            for _ in 0..d {
784                random_coeffs.push(Fq::rand(&mut test_rng()));
785            }
786            let res = Fq2::from_base_prime_field_elems(random_coeffs);
787            assert_eq!(res, None);
788        }
789        // Test on slice lengths that are equal to the extension degree
790        // We test consistency against Fq2::new
791        let number_of_tests = 10;
792        for _ in 0..number_of_tests {
793            let mut random_coeffs = Vec::new();
794            for _ in 0..ext_degree {
795                random_coeffs.push(Fq::rand(&mut test_rng()));
796            }
797            let expected = Fq2::new(random_coeffs[0], random_coeffs[1]);
798            let actual = Fq2::from_base_prime_field_elems(random_coeffs).unwrap();
799            assert_eq!(actual, expected);
800        }
801    }
802
803    #[test]
804    fn test_from_base_prime_field_element() {
805        let max_num_elems_to_test = 10;
806        for _ in 0..max_num_elems_to_test {
807            let mut random_coeffs = [Fq::zero(); 2];
808            let random_coeff = Fq::rand(&mut test_rng());
809            let res = Fq2::from_base_prime_field(random_coeff);
810            random_coeffs[0] = random_coeff;
811            assert_eq!(
812                res,
813                Fq2::from_base_prime_field_elems(random_coeffs).unwrap()
814            );
815        }
816    }
817}
ark_ff/fields/models/quadratic_extension.rs

ark_ff/fields/models/
quadratic_extension.rs
