p3_field/extension/
cubic_extension.rs

1//! Degree-3 extension field using the trinomial `X^3 - X - 1`.
2//!
3//! Reduction: `X^3 = X + 1`, so `X^4 = X^2 + X`.
4
5use alloc::format;
6use alloc::string::ToString;
7use alloc::vec::Vec;
8use core::array;
9use core::fmt::{self, Display, Formatter};
10use core::iter::{Product, Sum};
11use core::ops::{Add, AddAssign, Div, DivAssign, Mul, MulAssign, Neg, Sub, SubAssign};
12
13use itertools::Itertools;
14use num_bigint::BigUint;
15use p3_util::{as_base_slice, as_base_slice_mut, reconstitute_from_base};
16
17use super::packed_cubic_extension::PackedCubicTrinomialExtensionField;
18use super::{ExtField, HasFrobenius, HasTwoAdicCubicExtension};
19use crate::extension::{CubicTrinomial, CubicTrinomialExtendable, ExtensionAlgebra};
20use crate::field::Field;
21use crate::{
22    Algebra, ExtensionField, PackedFieldExtension, PrimeCharacteristicRing, RawDataSerializable,
23    TwoAdicField, field_to_array,
24};
25
26/// A degree-3 extension field using `X^3 - X - 1`.
27///
28/// Elements are `a_0 + a_1 X + a_2 X^2` with coefficients in the base field.
29///
30/// Type alias for the unified [`ExtField`] with `Shape = CubicTrinomial`.
31pub type CubicTrinomialExtensionField<F, A = F> = ExtField<F, 3, CubicTrinomial, A>;
32
33impl<F: Copy> CubicTrinomialExtensionField<F, F> {
34    /// Convert a `[[F; D]; N]` array to an array of extension field elements.
35    ///
36    /// Const version of `input.map(CubicTrinomialExtensionField::new)`.
37    ///
38    /// # Panics
39    /// Panics if `N == 0`.
40    #[inline]
41    pub const fn new_array<const N: usize>(input: [[F; 3]; N]) -> [Self; N] {
42        const { assert!(N > 0) }
43        let mut output = [Self::new(input[0]); N];
44        let mut i = 1;
45        while i < N {
46            output[i] = Self::new(input[i]);
47            i += 1;
48        }
49        output
50    }
51}
52
53impl<F: CubicTrinomialExtendable> ExtensionField<F> for CubicTrinomialExtensionField<F>
54where
55    PackedCubicTrinomialExtensionField<F, F::Packing>: PackedFieldExtension<F, Self>,
56{
57    type ExtensionPacking = PackedCubicTrinomialExtensionField<F, F::Packing>;
58
59    #[inline]
60    fn is_in_basefield(&self) -> bool {
61        self.value[1..].iter().all(F::is_zero)
62    }
63
64    #[inline]
65    fn as_base(&self) -> Option<F> {
66        <Self as ExtensionField<F>>::is_in_basefield(self).then(|| self.value[0])
67    }
68}
69
70impl<F: CubicTrinomialExtendable> HasFrobenius<F> for CubicTrinomialExtensionField<F> {
71    /// FrobeniusField automorphisms: x -> x^n, where n is the order of BaseField.
72    #[inline]
73    fn frobenius(&self) -> Self {
74        let a = &self.value;
75        let m = F::FROBENIUS_MATRIX;
76        let c0 = a[0] + F::dot_product::<2>(&[a[1], a[2]], &[m[0][1], m[0][2]]);
77        let c1 = F::dot_product::<2>(&[a[1], a[2]], &[m[1][1], m[1][2]]);
78        let c2 = F::dot_product::<2>(&[a[1], a[2]], &[m[2][1], m[2][2]]);
79        Self::new([c0, c1, c2])
80    }
81
82    /// Apply Frobenius `count` times: `x → x^{p^count}`.
83    #[inline]
84    fn repeated_frobenius(&self, count: usize) -> Self {
85        match count % 3 {
86            0 => *self,
87            _ => {
88                let mut result = *self;
89                for _ in 0..(count % 3) {
90                    result = result.frobenius();
91                }
92                result
93            }
94        }
95    }
96
97    /// Compute pseudo-inverse using Frobenius automorphism.
98    ///
99    /// Returns `0` if `self == 0`, and `1/self` otherwise.
100    ///
101    /// Uses the identity: `a^{-1} = ProdConj(a) * Norm(a)^{-1}` where
102    /// - `ProdConj(a) = a^{p + p^2}`,
103    /// - `Norm(a) = a * ProdConj(a)` is in the base field.
104    #[inline]
105    fn pseudo_inv(&self) -> Self {
106        if self.is_zero() {
107            return Self::ZERO;
108        }
109        let a_exp_p = self.frobenius();
110        let prod_conj = (*self * a_exp_p).frobenius();
111        let norm = self.compute_norm_with_prod_conj(&prod_conj);
112        debug_assert_eq!(Self::from(norm), *self * prod_conj);
113        prod_conj * norm.inverse()
114    }
115}
116
117impl<F: CubicTrinomialExtendable> CubicTrinomialExtensionField<F> {
118    /// Compute the norm given pre-computed product of conjugates.
119    ///
120    /// The norm `Norm(a) = a * prod_conj` lies in the base field.
121    /// This computes only the constant coefficient for efficiency.
122    #[inline]
123    fn compute_norm_with_prod_conj(&self, prod_conj: &Self) -> F {
124        let a = &self.value;
125        let b = &prod_conj.value;
126
127        // For trinomial X^3 - X - 1, the constant term of a*b is c_0 + c_3.
128        let c0 = a[0] * b[0];
129        let c3 = F::dot_product::<2>(&[a[1], a[2]], &[b[2], b[1]]);
130
131        c0 + c3
132    }
133}
134
135impl<F, A> PrimeCharacteristicRing for CubicTrinomialExtensionField<F, A>
136where
137    F: CubicTrinomialExtendable,
138    A: ExtensionAlgebra<F, 3, CubicTrinomial> + Copy,
139{
140    type PrimeSubfield = <A as PrimeCharacteristicRing>::PrimeSubfield;
141
142    const ZERO: Self = Self::new([A::ZERO; 3]);
143    const ONE: Self = Self::new(field_to_array(A::ONE));
144    const TWO: Self = Self::new(field_to_array(A::TWO));
145    const NEG_ONE: Self = Self::new(field_to_array(A::NEG_ONE));
146
147    #[inline]
148    fn from_prime_subfield(f: Self::PrimeSubfield) -> Self {
149        <A as PrimeCharacteristicRing>::from_prime_subfield(f).into()
150    }
151
152    #[inline]
153    fn halve(&self) -> Self {
154        Self::new(array::from_fn(|i| self.value[i].halve()))
155    }
156
157    #[inline(always)]
158    fn square(&self) -> Self {
159        let mut res = Self::default();
160        <A as ExtensionAlgebra<F, 3, CubicTrinomial>>::ext_square(&self.value, &mut res.value);
161        res
162    }
163
164    #[inline]
165    fn mul_2exp_u64(&self, exp: u64) -> Self {
166        Self::new(array::from_fn(|i| self.value[i].mul_2exp_u64(exp)))
167    }
168
169    #[inline]
170    fn div_2exp_u64(&self, exp: u64) -> Self {
171        Self::new(array::from_fn(|i| self.value[i].div_2exp_u64(exp)))
172    }
173
174    #[inline]
175    fn zero_vec(len: usize) -> Vec<Self> {
176        unsafe { reconstitute_from_base(A::zero_vec(len * 3)) }
177    }
178}
179
180impl<F: CubicTrinomialExtendable> Algebra<F> for CubicTrinomialExtensionField<F> {}
181
182impl<F: CubicTrinomialExtendable> RawDataSerializable for CubicTrinomialExtensionField<F> {
183    const NUM_BYTES: usize = F::NUM_BYTES * 3;
184
185    #[inline]
186    fn into_bytes(self) -> impl IntoIterator<Item = u8> {
187        self.value.into_iter().flat_map(|x| x.into_bytes())
188    }
189
190    #[inline]
191    fn into_byte_stream(input: impl IntoIterator<Item = Self>) -> impl IntoIterator<Item = u8> {
192        F::into_byte_stream(input.into_iter().flat_map(|x| x.value))
193    }
194
195    #[inline]
196    fn into_u32_stream(input: impl IntoIterator<Item = Self>) -> impl IntoIterator<Item = u32> {
197        F::into_u32_stream(input.into_iter().flat_map(|x| x.value))
198    }
199
200    #[inline]
201    fn into_u64_stream(input: impl IntoIterator<Item = Self>) -> impl IntoIterator<Item = u64> {
202        F::into_u64_stream(input.into_iter().flat_map(|x| x.value))
203    }
204
205    #[inline]
206    fn into_parallel_byte_streams<const N: usize>(
207        input: impl IntoIterator<Item = [Self; N]>,
208    ) -> impl IntoIterator<Item = [u8; N]> {
209        F::into_parallel_byte_streams(
210            input
211                .into_iter()
212                .flat_map(|x| (0..3).map(move |i| array::from_fn(|j| x[j].value[i]))),
213        )
214    }
215
216    #[inline]
217    fn into_parallel_u32_streams<const N: usize>(
218        input: impl IntoIterator<Item = [Self; N]>,
219    ) -> impl IntoIterator<Item = [u32; N]> {
220        F::into_parallel_u32_streams(
221            input
222                .into_iter()
223                .flat_map(|x| (0..3).map(move |i| array::from_fn(|j| x[j].value[i]))),
224        )
225    }
226
227    #[inline]
228    fn into_parallel_u64_streams<const N: usize>(
229        input: impl IntoIterator<Item = [Self; N]>,
230    ) -> impl IntoIterator<Item = [u64; N]> {
231        F::into_parallel_u64_streams(
232            input
233                .into_iter()
234                .flat_map(|x| (0..3).map(move |i| array::from_fn(|j| x[j].value[i]))),
235        )
236    }
237}
238
239impl<F: CubicTrinomialExtendable> crate::AlgebraIdentity<F> for CubicTrinomialExtensionField<F> {
240    fn algebra_id() -> Vec<u8> {
241        b"p3-power-basis-v1:X^3-X-1".to_vec()
242    }
243}
244
245impl<F: CubicTrinomialExtendable> Field for CubicTrinomialExtensionField<F> {
246    type Packing = Self;
247
248    const GENERATOR: Self = Self::new(F::EXT_GENERATOR);
249
250    fn try_inverse(&self) -> Option<Self> {
251        if self.is_zero() {
252            return None;
253        }
254        Some(self.pseudo_inv())
255    }
256
257    #[inline]
258    fn add_slices(slice_1: &mut [Self], slice_2: &[Self]) {
259        unsafe {
260            let base_slice_1 = as_base_slice_mut(slice_1);
261            let base_slice_2 = as_base_slice(slice_2);
262            F::add_slices(base_slice_1, base_slice_2);
263        }
264    }
265
266    #[inline]
267    fn order() -> BigUint {
268        F::order().pow(3)
269    }
270}
271
272impl<F: CubicTrinomialExtendable> Display for CubicTrinomialExtensionField<F> {
273    fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
274        if self.is_zero() {
275            write!(f, "0")
276        } else {
277            let str = self
278                .value
279                .iter()
280                .enumerate()
281                .filter(|(_, x)| !x.is_zero())
282                .map(|(i, x)| match (i, x.is_one()) {
283                    (0, _) => format!("{x}"),
284                    (1, true) => "X".to_string(),
285                    (1, false) => format!("{x} X"),
286                    (_, true) => format!("X^{i}"),
287                    (_, false) => format!("{x} X^{i}"),
288                })
289                .join(" + ");
290            write!(f, "{str}")
291        }
292    }
293}
294
295impl<F, A> Neg for CubicTrinomialExtensionField<F, A>
296where
297    F: CubicTrinomialExtendable,
298    A: Algebra<F>,
299{
300    type Output = Self;
301
302    #[inline]
303    fn neg(self) -> Self {
304        Self::new(self.value.map(A::neg))
305    }
306}
307
308impl<F, A> Add for CubicTrinomialExtensionField<F, A>
309where
310    F: CubicTrinomialExtendable,
311    A: ExtensionAlgebra<F, 3, CubicTrinomial>,
312{
313    type Output = Self;
314
315    #[inline]
316    fn add(self, rhs: Self) -> Self {
317        Self::new(<A as ExtensionAlgebra<F, 3, CubicTrinomial>>::ext_add(
318            &self.value,
319            &rhs.value,
320        ))
321    }
322}
323
324impl<F, A> Add<A> for CubicTrinomialExtensionField<F, A>
325where
326    F: CubicTrinomialExtendable,
327    A: Algebra<F>,
328{
329    type Output = Self;
330
331    #[inline]
332    fn add(mut self, rhs: A) -> Self {
333        self.value[0] += rhs;
334        self
335    }
336}
337
338impl<F, A> AddAssign for CubicTrinomialExtensionField<F, A>
339where
340    F: CubicTrinomialExtendable,
341    A: ExtensionAlgebra<F, 3, CubicTrinomial>,
342{
343    #[inline]
344    fn add_assign(&mut self, rhs: Self) {
345        self.value =
346            <A as ExtensionAlgebra<F, 3, CubicTrinomial>>::ext_add(&self.value, &rhs.value);
347    }
348}
349
350impl<F, A> AddAssign<A> for CubicTrinomialExtensionField<F, A>
351where
352    F: CubicTrinomialExtendable,
353    A: Algebra<F>,
354{
355    #[inline]
356    fn add_assign(&mut self, rhs: A) {
357        self.value[0] += rhs;
358    }
359}
360
361impl<F, A> Sum for CubicTrinomialExtensionField<F, A>
362where
363    F: CubicTrinomialExtendable,
364    A: ExtensionAlgebra<F, 3, CubicTrinomial> + Copy,
365{
366    #[inline]
367    fn sum<I: Iterator<Item = Self>>(iter: I) -> Self {
368        iter.reduce(|acc, x| acc + x).unwrap_or(Self::ZERO)
369    }
370}
371
372impl<F, A> Sub for CubicTrinomialExtensionField<F, A>
373where
374    F: CubicTrinomialExtendable,
375    A: ExtensionAlgebra<F, 3, CubicTrinomial>,
376{
377    type Output = Self;
378
379    #[inline]
380    fn sub(self, rhs: Self) -> Self {
381        Self::new(<A as ExtensionAlgebra<F, 3, CubicTrinomial>>::ext_sub(
382            &self.value,
383            &rhs.value,
384        ))
385    }
386}
387
388impl<F, A> Sub<A> for CubicTrinomialExtensionField<F, A>
389where
390    F: CubicTrinomialExtendable,
391    A: Algebra<F>,
392{
393    type Output = Self;
394
395    #[inline]
396    fn sub(self, rhs: A) -> Self {
397        let mut res = self.value;
398        res[0] -= rhs;
399        Self::new(res)
400    }
401}
402
403impl<F, A> SubAssign for CubicTrinomialExtensionField<F, A>
404where
405    F: CubicTrinomialExtendable,
406    A: ExtensionAlgebra<F, 3, CubicTrinomial>,
407{
408    #[inline]
409    fn sub_assign(&mut self, rhs: Self) {
410        self.value =
411            <A as ExtensionAlgebra<F, 3, CubicTrinomial>>::ext_sub(&self.value, &rhs.value);
412    }
413}
414
415impl<F, A> SubAssign<A> for CubicTrinomialExtensionField<F, A>
416where
417    F: CubicTrinomialExtendable,
418    A: Algebra<F>,
419{
420    #[inline]
421    fn sub_assign(&mut self, rhs: A) {
422        self.value[0] -= rhs;
423    }
424}
425
426impl<F, A> Mul for CubicTrinomialExtensionField<F, A>
427where
428    F: CubicTrinomialExtendable,
429    A: ExtensionAlgebra<F, 3, CubicTrinomial>,
430{
431    type Output = Self;
432
433    #[inline]
434    fn mul(self, rhs: Self) -> Self {
435        let mut res = Self::default();
436        <A as ExtensionAlgebra<F, 3, CubicTrinomial>>::ext_mul(
437            &self.value,
438            &rhs.value,
439            &mut res.value,
440        );
441        res
442    }
443}
444
445impl<F, A> Mul<A> for CubicTrinomialExtensionField<F, A>
446where
447    F: CubicTrinomialExtendable,
448    A: ExtensionAlgebra<F, 3, CubicTrinomial>,
449{
450    type Output = Self;
451
452    #[inline]
453    fn mul(self, rhs: A) -> Self {
454        Self::new(<A as ExtensionAlgebra<F, 3, CubicTrinomial>>::ext_base_mul(
455            self.value, rhs,
456        ))
457    }
458}
459
460impl<F, A> MulAssign for CubicTrinomialExtensionField<F, A>
461where
462    F: CubicTrinomialExtendable,
463    A: ExtensionAlgebra<F, 3, CubicTrinomial>,
464{
465    #[inline]
466    fn mul_assign(&mut self, rhs: Self) {
467        *self = self.clone() * rhs;
468    }
469}
470
471impl<F, A> MulAssign<A> for CubicTrinomialExtensionField<F, A>
472where
473    F: CubicTrinomialExtendable,
474    A: ExtensionAlgebra<F, 3, CubicTrinomial>,
475{
476    #[inline]
477    fn mul_assign(&mut self, rhs: A) {
478        *self = self.clone() * rhs;
479    }
480}
481
482impl<F, A> Product for CubicTrinomialExtensionField<F, A>
483where
484    F: CubicTrinomialExtendable,
485    A: ExtensionAlgebra<F, 3, CubicTrinomial> + Copy,
486{
487    #[inline]
488    fn product<I: Iterator<Item = Self>>(iter: I) -> Self {
489        iter.reduce(|acc, x| acc * x).unwrap_or(Self::ONE)
490    }
491}
492
493impl<F> Div for CubicTrinomialExtensionField<F>
494where
495    F: CubicTrinomialExtendable,
496{
497    type Output = Self;
498
499    #[allow(clippy::suspicious_arithmetic_impl)]
500    #[inline]
501    fn div(self, rhs: Self) -> Self::Output {
502        self * rhs.inverse()
503    }
504}
505
506impl<F> DivAssign for CubicTrinomialExtensionField<F>
507where
508    F: CubicTrinomialExtendable,
509{
510    #[inline]
511    fn div_assign(&mut self, rhs: Self) {
512        *self = *self / rhs;
513    }
514}
515
516impl<F: CubicTrinomialExtendable + HasTwoAdicCubicExtension> TwoAdicField
517    for CubicTrinomialExtensionField<F>
518{
519    const TWO_ADICITY: usize = F::EXT_TWO_ADICITY;
520
521    #[inline]
522    fn two_adic_generator(bits: usize) -> Self {
523        Self::new(F::ext_two_adic_generator(bits))
524    }
525}
526
527/// Multiply in `R[X]/(X^3 - X - 1)`.
528#[inline]
529pub fn trinomial_cubic_mul<R: PrimeCharacteristicRing>(a: &[R; 3], b: &[R; 3], res: &mut [R; 3]) {
530    let b0_plus_b2 = b[0].dup() + b[2].dup();
531    let b1_plus_b2 = b[1].dup() + b[2].dup();
532
533    res[0] = R::dot_product::<3>(a, &[b[0].dup(), b[2].dup(), b[1].dup()]);
534    res[1] = R::dot_product::<3>(a, &[b[1].dup(), b0_plus_b2.dup(), b1_plus_b2]);
535    res[2] = R::dot_product::<3>(a, &[b[2].dup(), b[1].dup(), b0_plus_b2]);
536}
537
538#[inline]
539pub fn cubic_square<R: PrimeCharacteristicRing>(a: &[R; 3], res: &mut [R; 3]) {
540    let a0_2 = a[0].double();
541    let a1_2 = a[1].double();
542    let two_a0_plus_a2 = a0_2.dup() + a[2].dup();
543    let two_a1_plus_a2 = a1_2.dup() + a[2].dup();
544
545    res[0] = R::dot_product::<2>(&[a[0].dup(), a1_2], &[a[0].dup(), a[2].dup()]);
546    res[1] = R::dot_product::<2>(&[a0_2, a[2].dup()], &[a[1].dup(), two_a1_plus_a2]);
547    res[2] = R::dot_product::<2>(&[a[1].dup(), a[2].dup()], &[a[1].dup(), two_a0_plus_a2]);
548}
p3_field/extension/cubic_extension.rs

p3_field/extension/
cubic_extension.rs
