p3_field/
field.rs

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

p3_field/
field.rs
