fgf 3.0.2

Faster Galois Fields: SIMD and portable finite-field arithmetic (binary towers and prime fields) and vector kernels
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69

//! Prime-field membership and integer reduction.
//!
//! [`PrimeField`] is the sealed degree-one capability: it marks the fields
//! that are GF(P) itself, across every presentation that supplies such a
//! row. It carries no methods; the shared [`Field`] surface is the
//! arithmetic, and the mathematical residue conversions live on each
//! element family. [`reduce`] and [`reduce_wide`] are the validated
//! `const` integer reductions, independent of any element or presentation
//! type.

use super::binary::BinaryRepr;
use super::finite_field::{FiniteField, Residue};
use super::goldilocks::Goldilocks;
use super::mersenne31::Mersenne31;
use super::{Field, is_prime, private};

/// A field of degree one: GF(P) itself.
///
/// Sealed marker over the degree-one rows, with no methods of its own.
/// Extensions and other higher-degree rows are excluded by construction,
/// not by a runtime check. Generic code bounds on this trait receive the
/// full [`Field`] surface plus the guarantee that every element is a
/// residue of the characteristic.
pub trait PrimeField: Field + private::PrimeFieldSeal {}

impl<const P: u64> private::PrimeFieldSeal for FiniteField<P, 1, Residue> {}

impl<const P: u64> PrimeField for FiniteField<P, 1, Residue> {}

impl private::PrimeFieldSeal for Mersenne31 {}

impl PrimeField for Mersenne31 {}

impl private::PrimeFieldSeal for Goldilocks {}

impl PrimeField for Goldilocks {}

impl<R: BinaryRepr<1>> private::PrimeFieldSeal for FiniteField<2, 1, R> {}

impl<R: BinaryRepr<1>> PrimeField for FiniteField<2, 1, R> {}

/// Reduce a `u64` to its ordinary residue modulo the prime `P`.
///
/// `value % P`, guarded by the deterministic primality proof: an invalid
/// modulus fails const evaluation in const contexts and panics on first
/// call otherwise.
///
/// # Panics
/// Panics when `P` is not prime.
#[must_use]
pub const fn reduce<const P: u64>(value: u64) -> u64 {
    assert!(is_prime(P), "characteristic is not prime");
    value % P
}

/// Reduce a `u128` to its ordinary residue modulo the prime `P`.
///
/// `value % P` over the widened modulus, guarded by the same primality
/// proof as [`reduce`]. The residue is below every valid `P`, so it fits
/// `u64`.
///
/// # Panics
/// Panics when `P` is not prime.
#[must_use]
#[allow(clippy::cast_possible_truncation, clippy::cast_lossless)]
pub const fn reduce_wide<const P: u64>(value: u128) -> u64 {
    assert!(is_prime(P), "characteristic is not prime");
    (value % P as u128) as u64
}