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 AbstractExtensionField<Base: AbstractField>:
259    AbstractField
260    + From<Base>
261    + Add<Base, Output = Self>
262    + AddAssign<Base>
263    + Sub<Base, Output = Self>
264    + SubAssign<Base>
265    + Mul<Base, Output = Self>
266    + MulAssign<Base>
267{
268    const D: usize;
269
270    fn from_base(b: Base) -> Self;
271
272    /// Suppose this field extension is represented by the quotient
273    /// ring B[X]/(f(X)) where B is `Base` and f is an irreducible
274    /// polynomial of degree `D`. This function takes a slice `bs` of
275    /// length at most D, and constructs the field element
276    /// \sum_i bs[i] * X^i.
277    ///
278    /// NB: The value produced by this function fundamentally depends
279    /// on the choice of irreducible polynomial f. Care must be taken
280    /// to ensure portability if these values might ever be passed to
281    /// (or rederived within) another compilation environment where a
282    /// different f might have been used.
283    fn from_base_slice(bs: &[Base]) -> Self;
284
285    /// Similar to `core:array::from_fn`, with the same caveats as
286    /// `from_base_slice`.
287    fn from_base_fn<F: FnMut(usize) -> Base>(f: F) -> Self;
288
289    /// Suppose this field extension is represented by the quotient
290    /// ring B[X]/(f(X)) where B is `Base` and f is an irreducible
291    /// polynomial of degree `D`. This function takes a field element
292    /// \sum_i bs[i] * X^i and returns the coefficients as a slice
293    /// `bs` of length at most D containing, from lowest degree to
294    /// highest.
295    ///
296    /// NB: The value produced by this function fundamentally depends
297    /// on the choice of irreducible polynomial f. Care must be taken
298    /// to ensure portability if these values might ever be passed to
299    /// (or rederived within) another compilation environment where a
300    /// different f might have been used.
301    fn as_base_slice(&self) -> &[Base];
302
303    /// Suppose this field extension is represented by the quotient
304    /// ring B[X]/(f(X)) where B is `Base` and f is an irreducible
305    /// polynomial of degree `D`. This function returns the field
306    /// element `X^exponent` if `exponent < D` and panics otherwise.
307    /// (The fact that f is not known at the point that this function
308    /// is defined prevents implementing exponentiation of higher
309    /// powers since the reduction cannot be performed.)
310    ///
311    /// NB: The value produced by this function fundamentally depends
312    /// on the choice of irreducible polynomial f. Care must be taken
313    /// to ensure portability if these values might ever be passed to
314    /// (or rederived within) another compilation environment where a
315    /// different f might have been used.
316    fn monomial(exponent: usize) -> Self {
317        assert!(exponent < Self::D, "requested monomial of too high degree");
318        let mut vec = vec![Base::zero(); Self::D];
319        vec[exponent] = Base::one();
320        Self::from_base_slice(&vec)
321    }
322}
323
324pub trait ExtensionField<Base: Field>: Field + AbstractExtensionField<Base> {
325    type ExtensionPacking: AbstractExtensionField<Base::Packing, F = Self>
326        + 'static
327        + Copy
328        + Send
329        + Sync;
330
331    fn is_in_basefield(&self) -> bool {
332        self.as_base_slice()[1..].iter().all(Field::is_zero)
333    }
334    fn as_base(&self) -> Option<Base> {
335        if self.is_in_basefield() {
336            Some(self.as_base_slice()[0])
337        } else {
338            None
339        }
340    }
341}
342
343impl<F: Field> ExtensionField<F> for F {
344    type ExtensionPacking = F::Packing;
345}
346
347impl<AF: AbstractField> AbstractExtensionField<AF> for AF {
348    const D: usize = 1;
349
350    fn from_base(b: AF) -> Self {
351        b
352    }
353
354    fn from_base_slice(bs: &[AF]) -> Self {
355        assert_eq!(bs.len(), 1);
356        bs[0].clone()
357    }
358
359    fn from_base_fn<F: FnMut(usize) -> AF>(mut f: F) -> Self {
360        f(0)
361    }
362
363    fn as_base_slice(&self) -> &[AF] {
364        slice::from_ref(self)
365    }
366}
367
368/// A field which supplies information like the two-adicity of its multiplicative group, and methods
369/// for obtaining two-adic generators.
370pub trait TwoAdicField: Field {
371    /// The number of factors of two in this field's multiplicative group.
372    const TWO_ADICITY: usize;
373
374    /// Returns a generator of the multiplicative group of order `2^bits`.
375    /// Assumes `bits < TWO_ADICITY`, otherwise the result is undefined.
376    #[must_use]
377    fn two_adic_generator(bits: usize) -> Self;
378}
379
380/// An iterator over the powers of a certain base element `b`: `b^0, b^1, b^2, ...`.
381#[derive(Clone, Debug)]
382pub struct Powers<F> {
383    pub base: F,
384    pub current: F,
385}
386
387impl<AF: AbstractField> Iterator for Powers<AF> {
388    type Item = AF;
389
390    fn next(&mut self) -> Option<AF> {
391        let result = self.current.clone();
392        self.current = self.current.clone() * self.base.clone();
393        Some(result)
394    }
395}
396
397/// like `Powers`, but packed into `PackedField` elements
398#[derive(Clone, Debug)]
399pub struct PackedPowers<F, P: PackedField<Scalar = F>> {
400    // base ** P::WIDTH
401    pub multiplier: P,
402    pub current: P,
403}
404
405impl<AF: AbstractField, P: PackedField<Scalar = AF>> Iterator for PackedPowers<AF, P> {
406    type Item = P;
407
408    fn next(&mut self) -> Option<P> {
409        let result = self.current;
410        self.current *= self.multiplier;
411        Some(result)
412    }
413}
p3_field/field.rs

p3_field/
field.rs
