Struct MontyField31

pub struct MontyField31<MP: MontyParameters> { /* private fields */ }

Implementations

impl<MP: MontyParameters + TwoAdicData> MontyField31<MP>

pub fn backward_fft(a: &mut [Self], root_table: &[Vec<Self>])

impl<MP: FieldParameters + TwoAdicData> MontyField31<MP>

pub fn roots_of_unity_table(n: usize) -> Vec<Vec<Self>>

Given a field element gen of order n where n = 2^lg_n, return a vector of vectors table where table[i] is the vector of twiddle factors for an fft of length n/2^i. The values gen^0 = 1 are skipped, as are g_i^k for k >= i/2 as these are just the negatives of the other roots (using g_i^{i/2} = -1).

impl<MP: MontyParameters + TwoAdicData> MontyField31<MP>

pub fn forward_fft(a: &mut [Self], root_table: &[Vec<Self>])

impl<MP: MontyParameters> MontyField31<MP>

pub const fn new(value: u32) -> Self

pub const fn new_array<const N: usize>(input: [u32; N]) -> [Self; N]

Convert a constant u32 array into a constant array of field elements. Constant version of array.map(MontyField31::new).

pub const fn new_2d_array<const N: usize, const M: usize>( input: [[u32; N]; M], ) -> [[Self; N]; M]

Convert a constant 2d u32 array into a constant 2d array of field elements. Constant version of array.map(MontyField31::new_array).

pub const fn mul_2exp_neg_n(&self, n: u32) -> Self

Multiply the given MontyField31 element by 2^{-n}.

This makes use of the fact that, as the monty constant is 2^32, the monty form of 2^{-n} is 2^{32 - n}. Monty reduction works provided the input is < 2^32P so this works for 0 <= n <= 32.

Trait Implementations

impl<FP: FieldParameters> AbstractField for MontyField31<FP>

const ZERO: Self = FP::MONTY_ZERO

const ONE: Self = FP::MONTY_ONE

const TWO: Self = FP::MONTY_TWO

const NEG_ONE: Self = FP::MONTY_NEG_ONE

type F = MontyField31<FP>

fn from_f(f: Self::F) -> Self

fn from_bool(b: bool) -> Self

Convert from a bool.

fn from_canonical_u8(n: u8) -> Self

Convert from a canonical u8.

fn from_canonical_u16(n: u16) -> Self

Convert from a canonical u16.

fn from_canonical_u32(n: u32) -> Self

Convert from a canonical u32.

fn from_canonical_u64(n: u64) -> Self

Convert from a canonical u64.

fn from_canonical_usize(n: usize) -> Self

Convert from a canonical usize.

fn from_wrapped_u32(n: u32) -> Self

fn from_wrapped_u64(n: u64) -> Self

fn mul_2exp_u64(&self, exp: u64) -> Self

self * 2^exp

fn zero_vec(len: usize) -> Vec<Self>

Allocates a vector of zero elements of length len. Many operating systems zero pages before assigning them to a userspace process. In that case, our process should not need to write zeros, which would be redundant. However, the compiler may not always recognize this.

fn double(&self) -> Self

fn square(&self) -> Self

fn cube(&self) -> Self

fn exp_u64(&self, power: u64) -> Self

Exponentiation by a u64 power.

fn exp_const_u64<const POWER: u64>(&self) -> Self

fn exp_power_of_2(&self, power_log: usize) -> Self

fn powers(&self) -> Powers<Self>

fn shifted_powers(&self, start: Self) -> Powers<Self>

fn powers_packed<P>(&self) -> PackedPowers<Self, P>

where P: PackedField<Scalar = Self>,

fn shifted_powers_packed<P>(&self, start: Self) -> PackedPowers<Self, P>

where P: PackedField<Scalar = Self>,

fn dot_product<const N: usize>(u: &[Self; N], v: &[Self; N]) -> Self

fn try_div<Rhs>(self, rhs: Rhs) -> Option<Self::Output>

where Rhs: Field, Self: Mul<Rhs>,

impl<PMP: PackedMontyParameters> Add<MontyField31<PMP>> for PackedMontyField31Neon<PMP>

type Output = PackedMontyField31Neon<PMP>

The resulting type after applying the + operator.

fn add(self, rhs: MontyField31<PMP>) -> Self

Performs the + operation.

impl<PMP: PackedMontyParameters> Add<PackedMontyField31Neon<PMP>> for MontyField31<PMP>

type Output = PackedMontyField31Neon<PMP>

The resulting type after applying the + operator.

fn add(self, rhs: PackedMontyField31Neon<PMP>) -> PackedMontyField31Neon<PMP>

Performs the + operation.

impl<FP: MontyParameters> Add for MontyField31<FP>

type Output = MontyField31<FP>

The resulting type after applying the + operator.

fn add(self, rhs: Self) -> Self

Performs the + operation.

impl<PMP: PackedMontyParameters> AddAssign<MontyField31<PMP>> for PackedMontyField31Neon<PMP>

fn add_assign(&mut self, rhs: MontyField31<PMP>)

Performs the += operation.

impl<FP: MontyParameters> AddAssign for MontyField31<FP>

fn add_assign(&mut self, rhs: Self)

Performs the += operation.

impl<const WIDTH: usize, FP> BinomiallyExtendable<WIDTH> for MontyField31<FP>

where FP: BinomialExtensionData<WIDTH> + FieldParameters,

const W: Self = _

const DTH_ROOT: Self = _

const EXT_GENERATOR: [Self; WIDTH] = FP::EXT_GENERATOR

impl<MP: Clone + MontyParameters> Clone for MontyField31<MP>

fn clone(&self) -> MontyField31<MP>

Returns a copy of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<FP: MontyParameters> Debug for MontyField31<FP>

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<MP: Default + MontyParameters> Default for MontyField31<MP>

fn default() -> MontyField31<MP>

Returns the “default value” for a type.

impl<'de, FP: FieldParameters> Deserialize<'de> for MontyField31<FP>

fn deserialize<D: Deserializer<'de>>(d: D) -> Result<Self, D::Error>

Deserialize this value from the given Serde deserializer.

impl<FP: MontyParameters> Display for MontyField31<FP>

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<FP: MontyParameters> Distribution<MontyField31<FP>> for Standard

fn sample<R: Rng + ?Sized>(&self, rng: &mut R) -> MontyField31<FP>

Generate a random value of T, using rng as the source of randomness.

fn sample_iter<R>(self, rng: R) -> DistIter<Self, R, T>

where R: Rng, Self: Sized,

Create an iterator that generates random values of T, using rng as the source of randomness.

fn map<F, S>(self, func: F) -> DistMap<Self, F, T, S>

where F: Fn(T) -> S, Self: Sized,

Create a distribution of values of ‘S’ by mapping the output of Self through the closure F

impl<FP: FieldParameters> Div<MontyField31<FP>> for PackedMontyField31Neon<FP>

type Output = PackedMontyField31Neon<FP>

The resulting type after applying the / operator.

fn div(self, rhs: MontyField31<FP>) -> Self

Performs the / operation.

impl<FP: FieldParameters> Div for MontyField31<FP>

type Output = MontyField31<FP>

The resulting type after applying the / operator.

fn div(self, rhs: Self) -> Self

Performs the / operation.

impl<FP, const WIDTH: usize, const D: u64> ExternalLayer<MontyField31<FP>, WIDTH, D> for Poseidon2ExternalLayerMonty31<FP, WIDTH>

where FP: FieldParameters,

fn permute_state_initial(&self, state: &mut [MontyField31<FP>; WIDTH])

Perform the initial external layers of the Poseidon2 permutation on the given state.

fn permute_state_terminal(&self, state: &mut [MontyField31<FP>; WIDTH])

Perform the terminal external layers of the Poseidon2 permutation on the given state.

impl<FP: FieldParameters> Field for MontyField31<FP>

const GENERATOR: Self = FP::MONTY_GEN

A generator of this field’s entire multiplicative group.

type Packing = PackedMontyField31Neon<FP>

fn exp_u64_generic<AF: AbstractField<F = Self>>(val: AF, power: u64) -> AF

Exponentiation by a u64 power. This is similar to exp_u64, but more general in that it can be used with AbstractFields, not just this concrete field.

fn try_inverse(&self) -> Option<Self>

The multiplicative inverse of this field element, if it exists.

fn halve(&self) -> Self

Computes input/2. Should be overwritten by most field implementations to use bitshifts. Will error if the field characteristic is 2.

fn order() -> BigUint

fn is_zero(&self) -> bool

fn is_one(&self) -> bool

fn div_2exp_u64(&self, exp: u64) -> Self

self / 2^exp

fn inverse(&self) -> Self

fn multiplicative_group_factors() -> Vec<(BigUint, usize)>

A list of (factor, exponent) pairs.

fn bits() -> usize

impl<PMP: PackedMontyParameters> From<MontyField31<PMP>> for PackedMontyField31Neon<PMP>

fn from(value: MontyField31<PMP>) -> Self

Converts to this type from the input type.

impl<const WIDTH: usize, FP> HasTwoAdicBionmialExtension<WIDTH> for MontyField31<FP>

where FP: BinomialExtensionData<WIDTH> + TwoAdicData + FieldParameters,

const EXT_TWO_ADICITY: usize = _

fn ext_two_adic_generator(bits: usize) -> [Self; WIDTH]

Assumes the multiplicative group size has at least bits powers of two, otherwise the behavior is undefined.

impl<MP: Hash + MontyParameters> Hash for MontyField31<MP>

fn hash<__H: Hasher>(&self, state: &mut __H)

Feeds this value into the given Hasher.

fn hash_slice<H>(data: &[Self], state: &mut H)

where H: Hasher, Self: Sized,

Feeds a slice of this type into the given Hasher.

impl<FP, const WIDTH: usize, P2P, const D: u64> InternalLayer<MontyField31<FP>, WIDTH, D> for Poseidon2InternalLayerMonty31<FP, WIDTH, P2P>

where FP: FieldParameters, P2P: InternalLayerParameters<FP, WIDTH>,

fn permute_state(&self, state: &mut [MontyField31<FP>; WIDTH])

Perform the internal layers of the Poseidon2 permutation on the given state.

impl<PMP: PackedMontyParameters> Mul<MontyField31<PMP>> for PackedMontyField31Neon<PMP>

type Output = PackedMontyField31Neon<PMP>

The resulting type after applying the * operator.

fn mul(self, rhs: MontyField31<PMP>) -> Self

Performs the * operation.

impl<PMP: PackedMontyParameters> Mul<PackedMontyField31Neon<PMP>> for MontyField31<PMP>

type Output = PackedMontyField31Neon<PMP>

The resulting type after applying the * operator.

fn mul(self, rhs: PackedMontyField31Neon<PMP>) -> PackedMontyField31Neon<PMP>

Performs the * operation.

impl<FP: MontyParameters> Mul for MontyField31<FP>

type Output = MontyField31<FP>

The resulting type after applying the * operator.

fn mul(self, rhs: Self) -> Self

Performs the * operation.

impl<PMP: PackedMontyParameters> MulAssign<MontyField31<PMP>> for PackedMontyField31Neon<PMP>

fn mul_assign(&mut self, rhs: MontyField31<PMP>)

Performs the *= operation.

impl<FP: MontyParameters> MulAssign for MontyField31<FP>

fn mul_assign(&mut self, rhs: Self)

Performs the *= operation.

impl<FP: FieldParameters> Neg for MontyField31<FP>

type Output = MontyField31<FP>

The resulting type after applying the - operator.

fn neg(self) -> Self::Output

Performs the unary - operation.

impl<FP: MontyParameters> Ord for MontyField31<FP>

fn cmp(&self, other: &Self) -> Ordering

This method returns an Ordering between self and other.

fn max(self, other: Self) -> Self

where Self: Sized,

Compares and returns the maximum of two values.

fn min(self, other: Self) -> Self

where Self: Sized,

Compares and returns the minimum of two values.

fn clamp(self, min: Self, max: Self) -> Self

where Self: Sized,

Restrict a value to a certain interval.

impl<MP: PartialEq + MontyParameters> PartialEq for MontyField31<MP>

fn eq(&self, other: &MontyField31<MP>) -> bool

Tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Rhs) -> bool

Tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl<FP: MontyParameters> PartialOrd for MontyField31<FP>

fn partial_cmp(&self, other: &Self) -> Option<Ordering>

This method returns an ordering between self and other values if one exists.

fn lt(&self, other: &Rhs) -> bool

Tests less than (for self and other) and is used by the < operator.

fn le(&self, other: &Rhs) -> bool

Tests less than or equal to (for self and other) and is used by the <= operator.

fn gt(&self, other: &Rhs) -> bool

Tests greater than (for self and other) and is used by the > operator.

fn ge(&self, other: &Rhs) -> bool

Tests greater than or equal to (for self and other) and is used by the >= operator.

impl<FP: FieldParameters> PrimeField for MontyField31<FP>

fn as_canonical_biguint(&self) -> BigUint

impl<FP: FieldParameters> PrimeField32 for MontyField31<FP>

const ORDER_U32: u32 = FP::PRIME

fn as_canonical_u32(&self) -> u32

Return the representative of value that is less than ORDER_U32.

impl<FP: FieldParameters> PrimeField64 for MontyField31<FP>

const ORDER_U64: u64 = _

fn as_canonical_u64(&self) -> u64

Return the representative of value that is less than ORDER_U64.

impl<FP: FieldParameters> Product<MontyField31<FP>> for PackedMontyField31Neon<FP>

fn product<I>(iter: I) -> Self

where I: Iterator<Item = MontyField31<FP>>,

Takes an iterator and generates Self from the elements by multiplying the items.

impl<FP: FieldParameters> Product for MontyField31<FP>

fn product<I: Iterator<Item = Self>>(iter: I) -> Self

Takes an iterator and generates Self from the elements by multiplying the items.

impl<FP: FieldParameters> Serialize for MontyField31<FP>

fn serialize<S: Serializer>(&self, serializer: S) -> Result<S::Ok, S::Error>

Serialize this value into the given Serde serializer.

impl<PMP: PackedMontyParameters> Sub<MontyField31<PMP>> for PackedMontyField31Neon<PMP>

type Output = PackedMontyField31Neon<PMP>

The resulting type after applying the - operator.

fn sub(self, rhs: MontyField31<PMP>) -> Self

Performs the - operation.

impl<PMP: PackedMontyParameters> Sub<PackedMontyField31Neon<PMP>> for MontyField31<PMP>

type Output = PackedMontyField31Neon<PMP>

The resulting type after applying the - operator.

fn sub(self, rhs: PackedMontyField31Neon<PMP>) -> PackedMontyField31Neon<PMP>

Performs the - operation.

impl<FP: MontyParameters> Sub for MontyField31<FP>

type Output = MontyField31<FP>

The resulting type after applying the - operator.

fn sub(self, rhs: Self) -> Self

Performs the - operation.

impl<PMP: PackedMontyParameters> SubAssign<MontyField31<PMP>> for PackedMontyField31Neon<PMP>

fn sub_assign(&mut self, rhs: MontyField31<PMP>)

Performs the -= operation.

impl<FP: MontyParameters> SubAssign for MontyField31<FP>

fn sub_assign(&mut self, rhs: Self)

Performs the -= operation.

impl<FP: FieldParameters> Sum<MontyField31<FP>> for PackedMontyField31Neon<FP>

fn sum<I>(iter: I) -> Self

where I: Iterator<Item = MontyField31<FP>>,

Takes an iterator and generates Self from the elements by “summing up” the items.

impl<FP: MontyParameters> Sum for MontyField31<FP>

fn sum<I: Iterator<Item = Self>>(iter: I) -> Self

Takes an iterator and generates Self from the elements by “summing up” the items.

impl<FP: FieldParameters + TwoAdicData> TwoAdicField for MontyField31<FP>

const TWO_ADICITY: usize = FP::TWO_ADICITY

The number of factors of two in this field’s multiplicative group.

fn two_adic_generator(bits: usize) -> Self

Returns a generator of the multiplicative group of order 2^bits. Assumes bits <= TWO_ADICITY, otherwise the result is undefined.

impl<MP: MontyParameters + FieldParameters + TwoAdicData> TwoAdicSubgroupDft<MontyField31<MP>> for RecursiveDft<MontyField31<MP>>

DFT implementation that uses DIT for the inverse “backward” direction and DIF for the “forward” direction.

The API mandates that the LDE is applied column-wise on the row-major input. This is awkward for memory coherence, so the algorithm here transposes the input and operates on the rows in the typical way, then transposes back again for the output. Even for modestly large inputs, the cost of the two tranposes outweighed by the improved performance from operating row-wise.

The choice of DIT for inverse and DIF for “forward” transform mean that a (coset) LDE

• IDFT / zero extend / DFT

expands to

• bit-reverse input
• invDFT DIT
  • result is in “correct” order
• coset shift and zero extend result
• DFT DIF on result
  • output is bit-reversed, as required for FRI.

Hence the only bit-reversal that needs to take place is on the input.

type Evaluations = RowIndexMappedView<BitReversalPerm, DenseMatrix<MontyField31<MP>>>

fn dft_batch(&self, mat: RowMajorMatrix<MontyField31<MP>>) -> Self::Evaluations

where MP: MontyParameters + FieldParameters + TwoAdicData,

Compute the discrete Fourier transform (DFT) of each column in mat. This is the only method an implementer needs to define, all other methods can be derived from this one.

fn idft_batch( &self, mat: RowMajorMatrix<MontyField31<MP>>, ) -> RowMajorMatrix<MontyField31<MP>>

where MP: MontyParameters + FieldParameters + TwoAdicData,

Compute the inverse DFT of each column in mat.

fn coset_lde_batch( &self, mat: RowMajorMatrix<MontyField31<MP>>, added_bits: usize, shift: MontyField31<MP>, ) -> Self::Evaluations

Compute the low-degree extension of each column in mat onto a coset of a larger subgroup.

fn dft(&self, vec: Vec<F>) -> Vec<F>

Compute the discrete Fourier transform (DFT) vec.

fn coset_dft(&self, vec: Vec<F>, shift: F) -> Vec<F>

Compute the “coset DFT” of vec. This can be viewed as interpolation onto a coset of a multiplicative subgroup, rather than the subgroup itself.

fn coset_dft_batch(&self, mat: DenseMatrix<F>, shift: F) -> Self::Evaluations

Compute the “coset DFT” of each column in mat. This can be viewed as interpolation onto a coset of a multiplicative subgroup, rather than the subgroup itself.

fn idft(&self, vec: Vec<F>) -> Vec<F>

Compute the inverse DFT of vec.

fn coset_idft(&self, vec: Vec<F>, shift: F) -> Vec<F>

Compute the “coset iDFT” of vec. This can be viewed as an inverse operation of “coset DFT”, that interpolates over a coset of a multiplicative subgroup, rather than subgroup itself.

fn coset_idft_batch(&self, mat: DenseMatrix<F>, shift: F) -> DenseMatrix<F>

Compute the “coset iDFT” of each column in mat. This can be viewed as an inverse operation of “coset DFT”, that interpolates over a coset of a multiplicative subgroup, rather than the subgroup itself.

fn lde(&self, vec: Vec<F>, added_bits: usize) -> Vec<F>

Compute the low-degree extension of vec onto a larger subgroup.

fn lde_batch(&self, mat: DenseMatrix<F>, added_bits: usize) -> Self::Evaluations

Compute the low-degree extension of each column in mat onto a larger subgroup.

fn coset_lde(&self, vec: Vec<F>, added_bits: usize, shift: F) -> Vec<F>

Compute the low-degree extension of each column in mat onto a coset of a larger subgroup.

impl<MP: Copy + MontyParameters> Copy for MontyField31<MP>

impl<MP: Eq + MontyParameters> Eq for MontyField31<MP>

impl<FP: MontyParameters, MU: MDSUtils> MdsPermutation<MontyField31<FP>, 12> for MdsMatrixMontyField31<MU>

impl<FP: MontyParameters, MU: MDSUtils> MdsPermutation<MontyField31<FP>, 16> for MdsMatrixMontyField31<MU>

impl<FP: BarrettParameters, MU: MDSUtils> MdsPermutation<MontyField31<FP>, 24> for MdsMatrixMontyField31<MU>

impl<FP: BarrettParameters, MU: MDSUtils> MdsPermutation<MontyField31<FP>, 32> for MdsMatrixMontyField31<MU>

impl<FP: BarrettParameters, MU: MDSUtils> MdsPermutation<MontyField31<FP>, 64> for MdsMatrixMontyField31<MU>

impl<FP: MontyParameters, MU: MDSUtils> MdsPermutation<MontyField31<FP>, 8> for MdsMatrixMontyField31<MU>

impl<FP: FieldParameters> Packable for MontyField31<FP>

impl<MP: MontyParameters> StructuralPartialEq for MontyField31<MP>