p3_field/
field.rs

1use alloc::vec;
2use alloc::vec::Vec;
3use core::fmt::{Debug, Display};
4use core::hash::Hash;
5use core::iter::{Product, Sum};
6use core::ops::{Add, AddAssign, Div, Mul, MulAssign, Neg, Sub, SubAssign};
7use core::slice;
8
9use itertools::Itertools;
10use num_bigint::BigUint;
11use num_traits::One;
12use nums::{Factorizer, FactorizerFromSplitter, MillerRabin, PollardRho};
13use serde::de::DeserializeOwned;
14use serde::Serialize;
15
16use crate::exponentiation::exp_u64_by_squaring;
17use crate::packed::{PackedField, PackedValue};
18use crate::Packable;
19
20/// A generalization of `Field` which permits things like
21/// - an actual field element
22/// - a symbolic expression which would evaluate to a field element
23/// - a vector of field elements
24pub trait AbstractField:
25    Sized
26    + Default
27    + Clone
28    + Add<Output = Self>
29    + AddAssign
30    + Sub<Output = Self>
31    + SubAssign
32    + Neg<Output = Self>
33    + Mul<Output = Self>
34    + MulAssign
35    + Sum
36    + Product
37    + Debug
38{
39    type F: Field;
40
41    fn zero() -> Self;
42    fn one() -> Self;
43    fn two() -> Self;
44    fn neg_one() -> Self;
45
46    fn from_f(f: Self::F) -> Self;
47    fn from_bool(b: bool) -> Self;
48    fn from_canonical_u8(n: u8) -> Self;
49    fn from_canonical_u16(n: u16) -> Self;
50    fn from_canonical_u32(n: u32) -> Self;
51    fn from_canonical_u64(n: u64) -> Self;
52    fn from_canonical_usize(n: usize) -> Self;
53
54    fn from_wrapped_u32(n: u32) -> Self;
55    fn from_wrapped_u64(n: u64) -> Self;
56
57    /// A generator of this field's entire multiplicative group.
58    fn generator() -> Self;
59
60    #[must_use]
61    fn double(&self) -> Self {
62        self.clone() + self.clone()
63    }
64
65    #[must_use]
66    fn square(&self) -> Self {
67        self.clone() * self.clone()
68    }
69
70    #[must_use]
71    fn cube(&self) -> Self {
72        self.square() * self.clone()
73    }
74
75    /// Exponentiation by a `u64` power.
76    ///
77    /// The default implementation calls `exp_u64_generic`, which by default performs exponentiation
78    /// by squaring. Rather than override this method, it is generally recommended to have the
79    /// concrete field type override `exp_u64_generic`, so that any optimizations will apply to all
80    /// abstract fields.
81    #[must_use]
82    #[inline]
83    fn exp_u64(&self, power: u64) -> Self {
84        Self::F::exp_u64_generic(self.clone(), power)
85    }
86
87    #[must_use]
88    #[inline(always)]
89    fn exp_const_u64<const POWER: u64>(&self) -> Self {
90        match POWER {
91            0 => Self::one(),
92            1 => self.clone(),
93            2 => self.square(),
94            3 => self.cube(),
95            4 => self.square().square(),
96            5 => self.square().square() * self.clone(),
97            6 => self.square().cube(),
98            7 => {
99                let x2 = self.square();
100                let x3 = x2.clone() * self.clone();
101                let x4 = x2.square();
102                x3 * x4
103            }
104            _ => self.exp_u64(POWER),
105        }
106    }
107
108    #[must_use]
109    fn exp_power_of_2(&self, power_log: usize) -> Self {
110        let mut res = self.clone();
111        for _ in 0..power_log {
112            res = res.square();
113        }
114        res
115    }
116
117    #[must_use]
118    fn powers(&self) -> Powers<Self> {
119        self.shifted_powers(Self::one())
120    }
121
122    fn shifted_powers(&self, start: Self) -> Powers<Self> {
123        Powers {
124            base: self.clone(),
125            current: start,
126        }
127    }
128
129    fn powers_packed<P: PackedField<Scalar = Self>>(&self) -> PackedPowers<Self, P> {
130        self.shifted_powers_packed(Self::one())
131    }
132
133    fn shifted_powers_packed<P: PackedField<Scalar = Self>>(
134        &self,
135        start: Self,
136    ) -> PackedPowers<Self, P> {
137        let mut current = P::from_f(start);
138        let slice = current.as_slice_mut();
139        for i in 1..P::WIDTH {
140            slice[i] = slice[i - 1].clone() * self.clone();
141        }
142
143        PackedPowers {
144            multiplier: P::from_f(self.clone()).exp_u64(P::WIDTH as u64),
145            current,
146        }
147    }
148
149    fn dot_product<const N: usize>(u: &[Self; N], v: &[Self; N]) -> Self {
150        u.iter().zip(v).map(|(x, y)| x.clone() * y.clone()).sum()
151    }
152
153    fn try_div<Rhs>(self, rhs: Rhs) -> Option<<Self as Mul<Rhs>>::Output>
154    where
155        Rhs: Field,
156        Self: Mul<Rhs>,
157    {
158        rhs.try_inverse().map(|inv| self * inv)
159    }
160}
161
162/// An element of a finite field.
163pub trait Field:
164    AbstractField<F = Self>
165    + Packable
166    + 'static
167    + Copy
168    + Div<Self, Output = Self>
169    + Eq
170    + Hash
171    + Send
172    + Sync
173    + Display
174    + Serialize
175    + DeserializeOwned
176{
177    type Packing: PackedField<Scalar = Self>;
178
179    fn is_zero(&self) -> bool {
180        *self == Self::zero()
181    }
182
183    fn is_one(&self) -> bool {
184        *self == Self::one()
185    }
186
187    /// self * 2^exp
188    #[must_use]
189    #[inline]
190    fn mul_2exp_u64(&self, exp: u64) -> Self {
191        *self * Self::two().exp_u64(exp)
192    }
193
194    /// self / 2^exp
195    #[must_use]
196    #[inline]
197    fn div_2exp_u64(&self, exp: u64) -> Self {
198        *self / Self::two().exp_u64(exp)
199    }
200
201    /// Exponentiation by a `u64` power. This is similar to `exp_u64`, but more general in that it
202    /// can be used with `AbstractField`s, not just this concrete field.
203    ///
204    /// The default implementation uses naive square and multiply. Implementations may want to
205    /// override this and handle certain powers with more optimal addition chains.
206    #[must_use]
207    #[inline]
208    fn exp_u64_generic<AF: AbstractField<F = Self>>(val: AF, power: u64) -> AF {
209        exp_u64_by_squaring(val, power)
210    }
211
212    /// The multiplicative inverse of this field element, if it exists.
213    ///
214    /// NOTE: The inverse of `0` is undefined and will return `None`.
215    #[must_use]
216    fn try_inverse(&self) -> Option<Self>;
217
218    #[must_use]
219    fn inverse(&self) -> Self {
220        self.try_inverse().expect("Tried to invert zero")
221    }
222
223    /// Computes input/2.
224    /// Should be overwritten by most field implementations to use bitshifts.
225    /// Will error if the field characteristic is 2.
226    #[must_use]
227    fn halve(&self) -> Self {
228        let half = Self::two()
229            .try_inverse()
230            .expect("Cannot divide by 2 in fields with characteristic 2");
231        *self * half
232    }
233
234    fn order() -> BigUint;
235
236    /// A list of (factor, exponent) pairs.
237    fn multiplicative_group_factors() -> Vec<(BigUint, usize)> {
238        let primality_test = MillerRabin { error_bits: 128 };
239        let composite_splitter = PollardRho;
240        let factorizer = FactorizerFromSplitter {
241            primality_test,
242            composite_splitter,
243        };
244        let n = Self::order() - BigUint::one();
245        factorizer.factor_counts(&n)
246    }
247
248    #[inline]
249    fn bits() -> usize {
250        Self::order().bits() as usize
251    }
252}
253
254pub trait PrimeField: Field + Ord {
255    fn as_canonical_biguint(&self) -> BigUint;
256}
257
258/// A prime field of order less than `2^64`.
259pub trait PrimeField64: PrimeField {
260    const ORDER_U64: u64;
261
262    /// Return the representative of `value` that is less than `ORDER_U64`.
263    fn as_canonical_u64(&self) -> u64;
264}
265
266/// A prime field of order less than `2^32`.
267pub trait PrimeField32: PrimeField64 {
268    const ORDER_U32: u32;
269
270    /// Return the representative of `value` that is less than `ORDER_U32`.
271    fn as_canonical_u32(&self) -> u32;
272}
273
274pub trait AbstractExtensionField<Base: AbstractField>:
275    AbstractField
276    + From<Base>
277    + Add<Base, Output = Self>
278    + AddAssign<Base>
279    + Sub<Base, Output = Self>
280    + SubAssign<Base>
281    + Mul<Base, Output = Self>
282    + MulAssign<Base>
283{
284    const D: usize;
285
286    fn from_base(b: Base) -> Self;
287
288    /// Suppose this field extension is represented by the quotient
289    /// ring B[X]/(f(X)) where B is `Base` and f is an irreducible
290    /// polynomial of degree `D`. This function takes a slice `bs` of
291    /// length at exactly D, and constructs the field element
292    /// \sum_i bs[i] * X^i.
293    ///
294    /// NB: The value produced by this function fundamentally depends
295    /// on the choice of irreducible polynomial f. Care must be taken
296    /// to ensure portability if these values might ever be passed to
297    /// (or rederived within) another compilation environment where a
298    /// different f might have been used.
299    fn from_base_slice(bs: &[Base]) -> Self;
300
301    /// Similar to `core:array::from_fn`, with the same caveats as
302    /// `from_base_slice`.
303    fn from_base_fn<F: FnMut(usize) -> Base>(f: F) -> Self;
304
305    /// Suppose this field extension is represented by the quotient
306    /// ring B[X]/(f(X)) where B is `Base` and f is an irreducible
307    /// polynomial of degree `D`. This function takes a field element
308    /// \sum_i bs[i] * X^i and returns the coefficients as a slice
309    /// `bs` of length at most D containing, from lowest degree to
310    /// highest.
311    ///
312    /// NB: The value produced by this function fundamentally depends
313    /// on the choice of irreducible polynomial f. Care must be taken
314    /// to ensure portability if these values might ever be passed to
315    /// (or rederived within) another compilation environment where a
316    /// different f might have been used.
317    fn as_base_slice(&self) -> &[Base];
318
319    /// Suppose this field extension is represented by the quotient
320    /// ring B[X]/(f(X)) where B is `Base` and f is an irreducible
321    /// polynomial of degree `D`. This function returns the field
322    /// element `X^exponent` if `exponent < D` and panics otherwise.
323    /// (The fact that f is not known at the point that this function
324    /// is defined prevents implementing exponentiation of higher
325    /// powers since the reduction cannot be performed.)
326    ///
327    /// NB: The value produced by this function fundamentally depends
328    /// on the choice of irreducible polynomial f. Care must be taken
329    /// to ensure portability if these values might ever be passed to
330    /// (or rederived within) another compilation environment where a
331    /// different f might have been used.
332    fn monomial(exponent: usize) -> Self {
333        assert!(exponent < Self::D, "requested monomial of too high degree");
334        let mut vec = vec![Base::zero(); Self::D];
335        vec[exponent] = Base::one();
336        Self::from_base_slice(&vec)
337    }
338}
339
340pub trait ExtensionField<Base: Field>: Field + AbstractExtensionField<Base> {
341    type ExtensionPacking: AbstractExtensionField<Base::Packing, F = Self>
342        + 'static
343        + Copy
344        + Send
345        + Sync;
346
347    fn is_in_basefield(&self) -> bool {
348        self.as_base_slice()[1..].iter().all(Field::is_zero)
349    }
350    fn as_base(&self) -> Option<Base> {
351        if self.is_in_basefield() {
352            Some(self.as_base_slice()[0])
353        } else {
354            None
355        }
356    }
357
358    fn ext_powers_packed(&self) -> impl Iterator<Item = Self::ExtensionPacking> {
359        let powers = self.powers().take(Base::Packing::WIDTH + 1).collect_vec();
360        // Transpose first WIDTH powers
361        let current = Self::ExtensionPacking::from_base_fn(|i| {
362            Base::Packing::from_fn(|j| powers[j].as_base_slice()[i])
363        });
364        // Broadcast self^WIDTH
365        let multiplier = Self::ExtensionPacking::from_base_fn(|i| {
366            Base::Packing::from(powers[Base::Packing::WIDTH].as_base_slice()[i])
367        });
368
369        core::iter::successors(Some(current), move |&current| Some(current * multiplier))
370    }
371}
372
373impl<F: Field> ExtensionField<F> for F {
374    type ExtensionPacking = F::Packing;
375}
376
377impl<AF: AbstractField> AbstractExtensionField<AF> for AF {
378    const D: usize = 1;
379
380    fn from_base(b: AF) -> Self {
381        b
382    }
383
384    fn from_base_slice(bs: &[AF]) -> Self {
385        assert_eq!(bs.len(), 1);
386        bs[0].clone()
387    }
388
389    fn from_base_fn<F: FnMut(usize) -> AF>(mut f: F) -> Self {
390        f(0)
391    }
392
393    fn as_base_slice(&self) -> &[AF] {
394        slice::from_ref(self)
395    }
396}
397
398/// A field which supplies information like the two-adicity of its multiplicative group, and methods
399/// for obtaining two-adic generators.
400pub trait TwoAdicField: Field {
401    /// The number of factors of two in this field's multiplicative group.
402    const TWO_ADICITY: usize;
403
404    /// Returns a generator of the multiplicative group of order `2^bits`.
405    /// Assumes `bits < TWO_ADICITY`, otherwise the result is undefined.
406    #[must_use]
407    fn two_adic_generator(bits: usize) -> Self;
408}
409
410/// An iterator over the powers of a certain base element `b`: `b^0, b^1, b^2, ...`.
411#[derive(Clone, Debug)]
412pub struct Powers<F> {
413    pub base: F,
414    pub current: F,
415}
416
417impl<AF: AbstractField> Iterator for Powers<AF> {
418    type Item = AF;
419
420    fn next(&mut self) -> Option<AF> {
421        let result = self.current.clone();
422        self.current *= self.base.clone();
423        Some(result)
424    }
425}
426
427/// like `Powers`, but packed into `PackedField` elements
428#[derive(Clone, Debug)]
429pub struct PackedPowers<F, P: PackedField<Scalar = F>> {
430    // base ** P::WIDTH
431    pub multiplier: P,
432    pub current: P,
433}
434
435impl<AF: AbstractField, P: PackedField<Scalar = AF>> Iterator for PackedPowers<AF, P> {
436    type Item = P;
437
438    fn next(&mut self) -> Option<P> {
439        let result = self.current;
440        self.current *= self.multiplier;
441        Some(result)
442    }
443}
p3_field/field.rs

p3_field/
field.rs
