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, Valid, Validate,
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: &'static [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)]
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    fn extension_degree() -> u64 {
216        2 * P::BaseField::extension_degree()
217    }
218
219    fn from_base_prime_field(elem: Self::BasePrimeField) -> Self {
220        let fe = P::BaseField::from_base_prime_field(elem);
221        Self::new(fe, P::BaseField::ZERO)
222    }
223
224    fn to_base_prime_field_elements(&self) -> impl Iterator<Item = Self::BasePrimeField> {
225        self.c0
226            .to_base_prime_field_elements()
227            .chain(self.c1.to_base_prime_field_elements())
228    }
229
230    fn from_base_prime_field_elems(
231        elems: impl IntoIterator<Item = Self::BasePrimeField>,
232    ) -> Option<Self> {
233        let mut elems = elems.into_iter();
234        let elems = elems.by_ref();
235        let base_ext_deg = P::BaseField::extension_degree() as usize;
236        let element = Some(Self::new(
237            P::BaseField::from_base_prime_field_elems(elems.take(base_ext_deg))?,
238            P::BaseField::from_base_prime_field_elems(elems.take(base_ext_deg))?,
239        ));
240        if elems.next().is_some() {
241            None
242        } else {
243            element
244        }
245    }
246
247    fn square(&self) -> Self {
248        let mut result = *self;
249        result.square_in_place();
250        result
251    }
252
253    #[inline]
254    fn from_random_bytes_with_flags<F: Flags>(bytes: &[u8]) -> Option<(Self, F)> {
255        let split_at = bytes.len() / 2;
256        if let Some(c0) = P::BaseField::from_random_bytes(&bytes[..split_at]) {
257            if let Some((c1, flags)) =
258                P::BaseField::from_random_bytes_with_flags(&bytes[split_at..])
259            {
260                return Some((QuadExtField::new(c0, c1), flags));
261            }
262        }
263        None
264    }
265
266    #[inline]
267    fn from_random_bytes(bytes: &[u8]) -> Option<Self> {
268        Self::from_random_bytes_with_flags::<EmptyFlags>(bytes).map(|f| f.0)
269    }
270
271    fn square_in_place(&mut self) -> &mut Self {
272        // (c0, c1)^2 = (c0 + x*c1)^2
273        //            = c0^2 + 2 c0 c1 x + c1^2 x^2
274        //            = c0^2 + beta * c1^2 + 2 c0 * c1 * x
275        //            = (c0^2 + beta * c1^2, 2 c0 * c1)
276        // Where beta is P::NONRESIDUE.
277        // When beta = -1, we can re-use intermediate additions to improve performance.
278        if P::NONRESIDUE == -P::BaseField::ONE {
279            // When the non-residue is -1, we save 2 intermediate additions,
280            // and use one fewer intermediate variable
281
282            let c0_copy = self.c0;
283            // v0 = c0 - c1
284            let mut v0 = self.c0;
285            v0 -= &self.c1;
286            self.c0 += self.c1;
287            // result.c0 *= (c0 - c1)
288            // result.c0 = (c0 - c1) * (c0 + c1) = c0^2 - c1^2
289            self.c0 *= &v0;
290
291            // result.c1 = 2 c1
292            self.c1.double_in_place();
293            // result.c1 *= c0
294            // result.c1 = (2 * c1) * c0
295            self.c1 *= &c0_copy;
296
297            self
298        } else {
299            // v0 = c0 - c1
300            let mut v0 = self.c0 - &self.c1;
301            // v3 = c0 - beta * c1
302            let mut v3 = self.c1;
303            P::sub_and_mul_base_field_by_nonresidue(&mut v3, &self.c0);
304            // v2 = c0 * c1
305            let v2 = self.c0 * &self.c1;
306
307            // v0 = (v0 * v3)
308            // v0 = (c0 - c1) * (c0 - beta*c1)
309            // v0 = c0^2 - beta * c0 * c1 - c0 * c1 + beta * c1^2
310            v0 *= &v3;
311
312            // result.c1 = 2 * c0 * c1
313            self.c1 = v2;
314            self.c1.double_in_place();
315            // result.c0 = (c0^2 - beta * c0 * c1 - c0 * c1 + beta * c1^2) + ((beta + 1) c0 * c1)
316            // result.c0 = (c0^2 - beta * c0 * c1 + beta * c1^2) + (beta * c0 * c1)
317            // result.c0 = c0^2 + beta * c1^2
318            self.c0 = v2;
319            P::mul_base_field_by_nonresidue_plus_one_and_add(&mut self.c0, &v0);
320
321            self
322        }
323    }
324
325    fn inverse(&self) -> Option<Self> {
326        if self.is_zero() {
327            None
328        } else {
329            // Guide to Pairing-based Cryptography, Algorithm 5.19.
330            // v1 = c1.square()
331            let v1 = self.c1.square();
332            // v0 = c0.square() - beta * v1
333            let mut v0 = v1;
334            P::sub_and_mul_base_field_by_nonresidue(&mut v0, &self.c0.square());
335
336            v0.inverse().map(|v1| {
337                let c0 = self.c0 * &v1;
338                let c1 = -(self.c1 * &v1);
339                Self::new(c0, c1)
340            })
341        }
342    }
343
344    fn inverse_in_place(&mut self) -> Option<&mut Self> {
345        if let Some(inverse) = self.inverse() {
346            *self = inverse;
347            Some(self)
348        } else {
349            None
350        }
351    }
352
353    fn frobenius_map_in_place(&mut self, power: usize) {
354        self.c0.frobenius_map_in_place(power);
355        self.c1.frobenius_map_in_place(power);
356        P::mul_base_field_by_frob_coeff(&mut self.c1, power);
357    }
358
359    fn legendre(&self) -> LegendreSymbol {
360        // The LegendreSymbol in a field of order q for an element x can be
361        // computed as x^((q-1)/2).
362        // Since we are in a quadratic extension of a field F_p,
363        // we have that q = p^2.
364        // Notice then that (q-1)/2 = ((p-1)/2) * (1 + p).
365        // This implies that we can compute the symbol as (x^(1+p))^((p-1)/2).
366        // Recall that computing x^(1 + p) is equivalent to taking the norm of x,
367        // and it will output an element in the base field F_p.
368        // Then exponentiating by (p-1)/2 in the base field is equivalent to computing
369        // the legendre symbol in the base field.
370        self.norm().legendre()
371    }
372
373    fn sqrt(&self) -> Option<Self> {
374        // Square root based on the complex method. See
375        // https://eprint.iacr.org/2012/685.pdf (page 15, algorithm 8)
376        if self.c1.is_zero() {
377            // for c = c0 + c1 * x, we have c1 = 0
378            // sqrt(c) == sqrt(c0) is an element of Fp2, i.e. sqrt(c0) = a = a0 + a1 * x for some a0, a1 in Fp
379            // squaring both sides: c0 = a0^2 + a1^2 * x^2 + (2 * a0 * a1 * x) = a0^2 + (a1^2 * P::NONRESIDUE)
380            // since there are no `x` terms on LHS, a0 * a1 = 0
381            // so either a0 = sqrt(c0) or a1 = sqrt(c0/P::NONRESIDUE)
382            if self.c0.legendre().is_qr() {
383                // either c0 is a valid sqrt in the base field
384                return self.c0.sqrt().map(|c0| Self::new(c0, P::BaseField::ZERO));
385            } else {
386                // or we need to compute sqrt(c0/P::NONRESIDUE)
387                return (self.c0.div(P::NONRESIDUE))
388                    .sqrt()
389                    .map(|res| Self::new(P::BaseField::ZERO, res));
390            }
391        }
392        // Try computing the square root
393        // Check at the end of the algorithm if it was a square root
394        let alpha = self.norm();
395
396        // Compute `(p+1)/2` as `1/2`.
397        // This is cheaper than `P::BaseField::one().double().inverse()`
398        let mut two_inv = P::BasePrimeField::MODULUS;
399
400        two_inv.add_with_carry(&1u64.into());
401        two_inv.div2();
402
403        let two_inv = P::BasePrimeField::from(two_inv);
404        let two_inv = P::BaseField::from_base_prime_field(two_inv);
405
406        alpha.sqrt().and_then(|alpha| {
407            let mut delta = (alpha + &self.c0) * &two_inv;
408            if delta.legendre().is_qnr() {
409                delta -= &alpha;
410            }
411            let c0 = delta.sqrt().expect("Delta must have a square root");
412            let c0_inv = c0.inverse().expect("c0 must have an inverse");
413            let sqrt_cand = Self::new(c0, self.c1 * &two_inv * &c0_inv);
414            // Check if sqrt_cand is actually the square root
415            // if not, there exists no square root.
416            if sqrt_cand.square() == *self {
417                Some(sqrt_cand)
418            } else {
419                #[cfg(debug_assertions)]
420                {
421                    use crate::fields::LegendreSymbol::*;
422                    if self.legendre() != QuadraticNonResidue {
423                        panic!(
424                            "Input has a square root per its legendre symbol, but it was not found"
425                        )
426                    }
427                }
428                None
429            }
430        })
431    }
432
433    fn sqrt_in_place(&mut self) -> Option<&mut Self> {
434        (*self).sqrt().map(|sqrt| {
435            *self = sqrt;
436            self
437        })
438    }
439
440    fn mul_by_base_prime_field(&self, elem: &Self::BasePrimeField) -> Self {
441        let mut result = *self;
442        result.c0 = result.c0.mul_by_base_prime_field(elem);
443        result.c1 = result.c1.mul_by_base_prime_field(elem);
444        result
445    }
446}
447
448/// `QuadExtField` elements are ordered lexicographically.
449impl<P: QuadExtConfig> Ord for QuadExtField<P> {
450    #[inline(always)]
451    fn cmp(&self, other: &Self) -> Ordering {
452        match self.c1.cmp(&other.c1) {
453            Ordering::Greater => Ordering::Greater,
454            Ordering::Less => Ordering::Less,
455            Ordering::Equal => self.c0.cmp(&other.c0),
456        }
457    }
458}
459
460impl<P: QuadExtConfig> PartialOrd for QuadExtField<P> {
461    #[inline(always)]
462    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
463        Some(self.cmp(other))
464    }
465}
466
467impl<P: QuadExtConfig> Zeroize for QuadExtField<P> {
468    // The phantom data does not contain element-specific data
469    // and thus does not need to be zeroized.
470    fn zeroize(&mut self) {
471        self.c0.zeroize();
472        self.c1.zeroize();
473    }
474}
475
476impl<P: QuadExtConfig> From<u128> for QuadExtField<P> {
477    fn from(other: u128) -> Self {
478        Self::new(other.into(), P::BaseField::ZERO)
479    }
480}
481
482impl<P: QuadExtConfig> From<i128> for QuadExtField<P> {
483    #[inline]
484    fn from(val: i128) -> Self {
485        let abs = Self::from(val.unsigned_abs());
486        if val.is_positive() {
487            abs
488        } else {
489            -abs
490        }
491    }
492}
493
494impl<P: QuadExtConfig> From<u64> for QuadExtField<P> {
495    fn from(other: u64) -> Self {
496        Self::new(other.into(), P::BaseField::ZERO)
497    }
498}
499
500impl<P: QuadExtConfig> From<i64> for QuadExtField<P> {
501    #[inline]
502    fn from(val: i64) -> Self {
503        let abs = Self::from(val.unsigned_abs());
504        if val.is_positive() {
505            abs
506        } else {
507            -abs
508        }
509    }
510}
511
512impl<P: QuadExtConfig> From<u32> for QuadExtField<P> {
513    fn from(other: u32) -> Self {
514        Self::new(other.into(), P::BaseField::ZERO)
515    }
516}
517
518impl<P: QuadExtConfig> From<i32> for QuadExtField<P> {
519    #[inline]
520    fn from(val: i32) -> Self {
521        let abs = Self::from(val.unsigned_abs());
522        if val.is_positive() {
523            abs
524        } else {
525            -abs
526        }
527    }
528}
529
530impl<P: QuadExtConfig> From<u16> for QuadExtField<P> {
531    fn from(other: u16) -> Self {
532        Self::new(other.into(), P::BaseField::ZERO)
533    }
534}
535
536impl<P: QuadExtConfig> From<i16> for QuadExtField<P> {
537    #[inline]
538    fn from(val: i16) -> Self {
539        let abs = Self::from(val.unsigned_abs());
540        if val.is_positive() {
541            abs
542        } else {
543            -abs
544        }
545    }
546}
547
548impl<P: QuadExtConfig> From<u8> for QuadExtField<P> {
549    fn from(other: u8) -> Self {
550        Self::new(other.into(), P::BaseField::ZERO)
551    }
552}
553
554impl<P: QuadExtConfig> From<i8> for QuadExtField<P> {
555    #[inline]
556    fn from(val: i8) -> Self {
557        let abs = Self::from(val.unsigned_abs());
558        if val.is_positive() {
559            abs
560        } else {
561            -abs
562        }
563    }
564}
565
566impl<P: QuadExtConfig> From<bool> for QuadExtField<P> {
567    fn from(other: bool) -> Self {
568        Self::new(u8::from(other).into(), P::BaseField::ZERO)
569    }
570}
571
572impl<P: QuadExtConfig> Neg for QuadExtField<P> {
573    type Output = Self;
574    #[inline]
575    #[must_use]
576    fn neg(mut self) -> Self {
577        self.c0.neg_in_place();
578        self.c1.neg_in_place();
579        self
580    }
581}
582
583impl<P: QuadExtConfig> Distribution<QuadExtField<P>> for Standard {
584    #[inline]
585    fn sample<R: Rng + ?Sized>(&self, rng: &mut R) -> QuadExtField<P> {
586        QuadExtField::new(UniformRand::rand(rng), UniformRand::rand(rng))
587    }
588}
589
590impl<'a, P: QuadExtConfig> Add<&'a QuadExtField<P>> for QuadExtField<P> {
591    type Output = Self;
592
593    #[inline]
594    fn add(mut self, other: &Self) -> Self {
595        self += other;
596        self
597    }
598}
599
600impl<'a, P: QuadExtConfig> Sub<&'a QuadExtField<P>> for QuadExtField<P> {
601    type Output = Self;
602
603    #[inline(always)]
604    fn sub(mut self, other: &Self) -> Self {
605        self -= other;
606        self
607    }
608}
609
610impl<'a, P: QuadExtConfig> Mul<&'a QuadExtField<P>> for QuadExtField<P> {
611    type Output = Self;
612
613    #[inline(always)]
614    fn mul(mut self, other: &Self) -> Self {
615        self *= other;
616        self
617    }
618}
619
620impl<'a, P: QuadExtConfig> Div<&'a QuadExtField<P>> for QuadExtField<P> {
621    type Output = Self;
622
623    #[inline]
624    fn div(mut self, other: &Self) -> Self {
625        self.mul_assign(&other.inverse().unwrap());
626        self
627    }
628}
629
630impl<'a, P: QuadExtConfig> AddAssign<&'a Self> for QuadExtField<P> {
631    #[inline]
632    fn add_assign(&mut self, other: &Self) {
633        self.c0 += &other.c0;
634        self.c1 += &other.c1;
635    }
636}
637
638impl<'a, P: QuadExtConfig> SubAssign<&'a Self> for QuadExtField<P> {
639    #[inline]
640    fn sub_assign(&mut self, other: &Self) {
641        self.c0 -= &other.c0;
642        self.c1 -= &other.c1;
643    }
644}
645
646impl_additive_ops_from_ref!(QuadExtField, QuadExtConfig);
647impl_multiplicative_ops_from_ref!(QuadExtField, QuadExtConfig);
648
649impl<'a, P: QuadExtConfig> MulAssign<&'a Self> for QuadExtField<P> {
650    #[inline]
651    fn mul_assign(&mut self, other: &Self) {
652        if Self::extension_degree() == 2 {
653            let c1_input = [self.c0, self.c1];
654            P::mul_base_field_by_nonresidue_in_place(&mut self.c1);
655            *self = Self::new(
656                P::BaseField::sum_of_products(&[self.c0, self.c1], &[other.c0, other.c1]),
657                P::BaseField::sum_of_products(&c1_input, &[other.c1, other.c0]),
658            )
659        } else {
660            // Karatsuba multiplication;
661            // Guide to Pairing-based cryprography, Algorithm 5.16.
662            let mut v0 = self.c0;
663            v0 *= &other.c0;
664            let mut v1 = self.c1;
665            v1 *= &other.c1;
666
667            self.c1 += &self.c0;
668            self.c1 *= &(other.c0 + &other.c1);
669            self.c1 -= &v0;
670            self.c1 -= &v1;
671            self.c0 = v1;
672            P::mul_base_field_by_nonresidue_and_add(&mut self.c0, &v0);
673        }
674    }
675}
676
677impl<'a, P: QuadExtConfig> DivAssign<&'a Self> for QuadExtField<P> {
678    #[inline]
679    fn div_assign(&mut self, other: &Self) {
680        self.mul_assign(&other.inverse().unwrap());
681    }
682}
683
684impl<P: QuadExtConfig> fmt::Display for QuadExtField<P> {
685    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
686        write!(f, "QuadExtField({} + {} * u)", self.c0, self.c1)
687    }
688}
689
690impl<P: QuadExtConfig> CanonicalSerializeWithFlags for QuadExtField<P> {
691    #[inline]
692    fn serialize_with_flags<W: Write, F: Flags>(
693        &self,
694        mut writer: W,
695        flags: F,
696    ) -> Result<(), SerializationError> {
697        self.c0.serialize_compressed(&mut writer)?;
698        self.c1.serialize_with_flags(&mut writer, flags)?;
699        Ok(())
700    }
701
702    #[inline]
703    fn serialized_size_with_flags<F: Flags>(&self) -> usize {
704        self.c0.compressed_size() + self.c1.serialized_size_with_flags::<F>()
705    }
706}
707
708impl<P: QuadExtConfig> CanonicalSerialize for QuadExtField<P> {
709    #[inline]
710    fn serialize_with_mode<W: Write>(
711        &self,
712        writer: W,
713        _compress: Compress,
714    ) -> Result<(), SerializationError> {
715        self.serialize_with_flags(writer, EmptyFlags)
716    }
717
718    #[inline]
719    fn serialized_size(&self, _compress: Compress) -> usize {
720        self.serialized_size_with_flags::<EmptyFlags>()
721    }
722}
723
724impl<P: QuadExtConfig> CanonicalDeserializeWithFlags for QuadExtField<P> {
725    #[inline]
726    fn deserialize_with_flags<R: Read, F: Flags>(
727        mut reader: R,
728    ) -> Result<(Self, F), SerializationError> {
729        let c0 = CanonicalDeserialize::deserialize_compressed(&mut reader)?;
730        let (c1, flags) = CanonicalDeserializeWithFlags::deserialize_with_flags(&mut reader)?;
731        Ok((QuadExtField::new(c0, c1), flags))
732    }
733}
734
735impl<P: QuadExtConfig> Valid for QuadExtField<P> {
736    fn check(&self) -> Result<(), SerializationError> {
737        self.c0.check()?;
738        self.c1.check()
739    }
740}
741
742impl<P: QuadExtConfig> CanonicalDeserialize for QuadExtField<P> {
743    #[inline]
744    fn deserialize_with_mode<R: Read>(
745        mut reader: R,
746        compress: Compress,
747        validate: Validate,
748    ) -> Result<Self, SerializationError> {
749        let c0: P::BaseField =
750            CanonicalDeserialize::deserialize_with_mode(&mut reader, compress, validate)?;
751        let c1: P::BaseField =
752            CanonicalDeserialize::deserialize_with_mode(&mut reader, compress, validate)?;
753        Ok(QuadExtField::new(c0, c1))
754    }
755}
756
757impl<P: QuadExtConfig> ToConstraintField<P::BasePrimeField> for QuadExtField<P>
758where
759    P::BaseField: ToConstraintField<P::BasePrimeField>,
760{
761    fn to_field_elements(&self) -> Option<Vec<P::BasePrimeField>> {
762        let mut res = Vec::new();
763        let mut c0_elems = self.c0.to_field_elements()?;
764        let mut c1_elems = self.c1.to_field_elements()?;
765
766        res.append(&mut c0_elems);
767        res.append(&mut c1_elems);
768
769        Some(res)
770    }
771}
772
773#[cfg(test)]
774mod quad_ext_tests {
775    use super::*;
776    use ark_std::test_rng;
777    use ark_test_curves::{
778        ark_ff::Field,
779        bls12_381::{Fq, Fq2},
780    };
781
782    #[test]
783    fn test_from_base_prime_field_elements() {
784        let ext_degree = Fq2::extension_degree() as usize;
785        // Test on slice lengths that aren't equal to the extension degree
786        let max_num_elems_to_test = 4;
787        for d in 0..max_num_elems_to_test {
788            if d == ext_degree {
789                continue;
790            }
791            let mut random_coeffs = Vec::<Fq>::new();
792            for _ in 0..d {
793                random_coeffs.push(Fq::rand(&mut test_rng()));
794            }
795            let res = Fq2::from_base_prime_field_elems(random_coeffs);
796            assert_eq!(res, None);
797        }
798        // Test on slice lengths that are equal to the extension degree
799        // We test consistency against Fq2::new
800        let number_of_tests = 10;
801        for _ in 0..number_of_tests {
802            let mut random_coeffs = Vec::<Fq>::new();
803            for _ in 0..ext_degree {
804                random_coeffs.push(Fq::rand(&mut test_rng()));
805            }
806            let expected = Fq2::new(random_coeffs[0], random_coeffs[1]);
807            let actual = Fq2::from_base_prime_field_elems(random_coeffs).unwrap();
808            assert_eq!(actual, expected);
809        }
810    }
811
812    #[test]
813    fn test_from_base_prime_field_element() {
814        let ext_degree = Fq2::extension_degree() as usize;
815        let max_num_elems_to_test = 10;
816        for _ in 0..max_num_elems_to_test {
817            let mut random_coeffs = vec![Fq::zero(); ext_degree];
818            let random_coeff = Fq::rand(&mut test_rng());
819            let res = Fq2::from_base_prime_field(random_coeff);
820            random_coeffs[0] = random_coeff;
821            assert_eq!(
822                res,
823                Fq2::from_base_prime_field_elems(random_coeffs).unwrap()
824            );
825        }
826    }
827}
828
829impl<P: QuadExtConfig> FftField for QuadExtField<P>
830where
831    P::BaseField: FftField,
832{
833    const GENERATOR: Self = Self::new(P::BaseField::GENERATOR, P::BaseField::ZERO);
834    const TWO_ADICITY: u32 = P::BaseField::TWO_ADICITY;
835    const TWO_ADIC_ROOT_OF_UNITY: Self =
836        Self::new(P::BaseField::TWO_ADIC_ROOT_OF_UNITY, P::BaseField::ZERO);
837    const SMALL_SUBGROUP_BASE: Option<u32> = P::BaseField::SMALL_SUBGROUP_BASE;
838    const SMALL_SUBGROUP_BASE_ADICITY: Option<u32> = P::BaseField::SMALL_SUBGROUP_BASE_ADICITY;
839    const LARGE_SUBGROUP_ROOT_OF_UNITY: Option<Self> =
840        if let Some(x) = P::BaseField::LARGE_SUBGROUP_ROOT_OF_UNITY {
841            Some(Self::new(x, P::BaseField::ZERO))
842        } else {
843            None
844        };
845}
ark_ff/fields/models/quadratic_extension.rs

ark_ff/fields/models/
quadratic_extension.rs
