Struct MontyField31 

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

Implementations

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

pub fn backward_fft(input: &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 g_i^k for k >= i/2 are skipped as these are just the negatives of the other roots (using g_i^{i/2} = -1). The value gen^0 = 1 is included to aid consistency between the packed and non-packed variants.

pub fn get_missing_twiddles(req_lg_n: usize, cur_lg_n: usize) -> Vec<Vec<Self>>

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

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

impl<MP: MontyParameters> MontyField31<MP>

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

The standard way to create a new element. Note that new converts the input into MONTY form so should be avoided in performance critical implementations.

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).

Trait Implementations

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<MP: MontyParameters, T: Into<Self>> AddAssign<T> for MontyField31<MP>

fn add_assign(&mut self, rhs: T)

Performs the += operation.

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

where FP: BinomialExtensionData<WIDTH> + FieldParameters,

const W: Self = FP::W

The constant coefficient W in the binomial X^D - W.

const DTH_ROOT: Self = FP::DTH_ROOT

A D-th root of unity derived from W.

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

A generator for the extension field, expressed as a degree-D polynomial.

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

where FP: BinomialExtensionData<WIDTH> + FieldParameters,

fn binomial_mul( a: &[Self; WIDTH], b: &[Self; WIDTH], res: &mut [Self; WIDTH], _w: Self, )

Multiplication in the algebra extension ring A<X> / (X^D - W).

fn binomial_add(a: &[Self; WIDTH], b: &[Self; WIDTH]) -> [Self; WIDTH]

Addition of elements in the algebra extension ring A<X> / (X^D - W).

fn binomial_sub(a: &[Self; WIDTH], b: &[Self; WIDTH]) -> [Self; WIDTH]

Subtraction of elements in the algebra extension ring A<X> / (X^D - W).

fn binomial_base_mul(lhs: [Self; WIDTH], rhs: Self) -> [Self; WIDTH]

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

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

Returns a duplicate 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 StandardUniform

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) -> Iter<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) -> Map<Self, F, T, S>

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

Map sampled values to type S

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

type Output = MontyField31<FP>

The resulting type after applying the / operator.

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

Performs the / operation.

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

fn div_assign(&mut self, rhs: MontyField31<FP>)

Performs the /= operation.

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

where FP: FieldParameters + RelativelyPrimePower<D>,

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, const WIDTH: usize> ExternalLayerConstructor<MontyField31<FP>, WIDTH> for Poseidon2ExternalLayerMonty31<FP, WIDTH>

fn new_from_constants( external_constants: ExternalLayerConstants<MontyField31<FP>, WIDTH>, ) -> Self

A constructor which internally will convert the supplied constants into the appropriate form for the implementation.

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

const GENERATOR: Self = FP::MONTY_GEN

A generator of this field’s multiplicative group.

type Packing = MontyField31<FP>

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

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

fn order() -> BigUint

The number of elements in the field.

fn is_zero(&self) -> bool

Check if the given field element is equal to the unique additive identity (ZERO).

fn is_one(&self) -> bool

Check if the given field element is equal to the unique multiplicative identity (ONE).

fn inverse(&self) -> Self

The multiplicative inverse of this field element.

fn add_slices(slice_1: &mut [Self], slice_2: &[Self])

Add two slices of field elements together, returning the result in the first slice.

fn bits() -> usize

The number of bits required to define an element of this field.

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

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

const EXT_TWO_ADICITY: usize = FP::EXT_TWO_ADICITY

Two-adicity of the multiplicative group of the extension field.

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

Returns a two-adic generator for the extension field.

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: FieldParameters + RelativelyPrimePower<D>, const D: u64> InjectiveMonomial<D> for MontyField31<FP>

fn injective_exp_n(&self) -> Self

Compute x -> x^n for a given n > 1 such that this map is injective.

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

where FP: FieldParameters + RelativelyPrimePower<D>, 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<FP: FieldParameters, const WIDTH: usize, ILP: InternalLayerBaseParameters<FP, WIDTH>> InternalLayerConstructor<MontyField31<FP>> for Poseidon2InternalLayerMonty31<FP, WIDTH, ILP>

fn new_from_constants(internal_constants: Vec<MontyField31<FP>>) -> Self

A constructor which internally will convert the supplied constants into the appropriate form for the implementation.

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<FP: FieldParameters, T: Into<Self>> MulAssign<T> for MontyField31<FP>

fn mul_assign(&mut self, rhs: T)

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 + RelativelyPrimePower<D>, const D: u64> PermutationMonomial<D> for MontyField31<FP>

fn injective_exp_root_n(&self) -> Self

Compute x -> x^K for a given K > 1 such that x^{NK} = x for all elements x.

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

const ZERO: Self = FP::MONTY_ZERO

The additive identity of the ring.

const ONE: Self = FP::MONTY_ONE

The multiplicative identity of the ring.

const TWO: Self = FP::MONTY_TWO

The element in the ring given by ONE + ONE.

const NEG_ONE: Self = FP::MONTY_NEG_ONE

The element in the ring given by -ONE.

type PrimeSubfield = MontyField31<FP>

The field ℤ/p where the characteristic of this ring is p.

fn from_prime_subfield(f: Self) -> Self

Embed an element of the prime field ℤ/p into the ring R.

fn halve(&self) -> Self

The elementary function halve(a) = a/2.

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

The elementary function mul_2exp_u64(a, exp) = a * 2^{exp}.

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

Divide by a given power of two. div_2exp_u64(a, exp) = a/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 sum_array<const N: usize>(input: &[Self]) -> Self

Compute the sum of a slice of elements whose length is a compile time constant.

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

Compute the dot product of two vectors.

fn from_bool(b: bool) -> Self

Return Self::ONE if b is true and Self::ZERO if b is false.

fn from_u8(int: u8) -> Self

Given an integer r, return the sum of r copies of ONE:

fn from_u16(int: u16) -> Self

Given an integer r, return the sum of r copies of ONE:

fn from_u32(int: u32) -> Self

Given an integer r, return the sum of r copies of ONE:

fn from_u64(int: u64) -> Self

Given an integer r, return the sum of r copies of ONE:

fn from_u128(int: u128) -> Self

Given an integer r, return the sum of r copies of ONE:

fn from_usize(int: usize) -> Self

Given an integer r, return the sum of r copies of ONE:

fn from_i8(int: i8) -> Self

Given an integer r, return the sum of r copies of ONE:

fn from_i16(int: i16) -> Self

Given an integer r, return the sum of r copies of ONE:

fn from_i32(int: i32) -> Self

Given an integer r, return the sum of r copies of ONE:

fn from_i64(int: i64) -> Self

Given an integer r, return the sum of r copies of ONE:

fn from_i128(int: i128) -> Self

Given an integer r, return the sum of r copies of ONE:

fn from_isize(int: isize) -> Self

Given an integer r, return the sum of r copies of ONE:

fn double(&self) -> Self

The elementary function double(a) = 2*a.

fn square(&self) -> Self

The elementary function square(a) = a^2.

fn cube(&self) -> Self

The elementary function cube(a) = a^3.

fn xor(&self, y: &Self) -> Self

Computes the arithmetic generalization of boolean xor.

fn xor3(&self, y: &Self, z: &Self) -> Self

Computes the arithmetic generalization of a triple xor.

fn andn(&self, y: &Self) -> Self

Computes the arithmetic generalization of andnot.

fn bool_check(&self) -> Self

The vanishing polynomial for boolean values: x * (1 - x).

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

Exponentiation by a u64 power.

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

Exponentiation by a small constant power.

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

The elementary function exp_power_of_2(a, power_log) = a^{2^power_log}.

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

Construct an iterator which returns powers of self: self^0, self^1, self^2, ....

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

Construct an iterator which returns powers of self shifted by start: start, start*self^1, start*self^2, ....

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

fn as_canonical_biguint(&self) -> BigUint

Return the representative of value in canonical form which lies in the range 0 <= x < self.order().

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

const ORDER_U32: u32 = FP::PRIME

fn as_canonical_u32(&self) -> u32

Return the representative of value in canonical form which lies in the range 0 <= x < ORDER_U64.

fn to_unique_u32(&self) -> u32

Convert a field element to a u32 such that any two field elements are converted to the same u32 if and only if they represent the same value.

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

const ORDER_U64: u64

fn as_canonical_u64(&self) -> u64

Return the representative of value in canonical form which lies in the range 0 <= x < ORDER_U64.

fn to_unique_u64(&self) -> u64

Convert a field element to a u64 such that any two field elements are converted to the same u64 if and only if they represent the same value.

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> QuotientMap<i128> for MontyField31<FP>

fn from_int(int: i128) -> Self

Convert a given i128 integer into an element of the MontyField31 field.

fn from_canonical_checked(int: i128) -> Option<Self>

Convert a given i128 integer into an element of the MontyField31 field.

Returns None if the given integer does not lie in the range [(1 - P)/2, (P - 1)/2].

unsafe fn from_canonical_unchecked(int: i128) -> Self

Convert a given i128 integer into an element of the MontyField31 field.

Safety

The input must be a valid i64 element.

impl<FP: FieldParameters> QuotientMap<i16> for MontyField31<FP>

fn from_int(int: i16) -> Self

Convert a given i16 integer into an element of the MontyField31 field.

Due to the integer type, the input value is always canonical.

fn from_canonical_checked(int: i16) -> Option<Self>

Convert a given i16 integer into an element of the MontyField31 field.

Due to the integer type, the input value is always canonical.

unsafe fn from_canonical_unchecked(int: i16) -> Self

Convert a given i16 integer into an element of the MontyField31 field.

Due to the integer type, the input value is always canonical.

impl<FP: FieldParameters> QuotientMap<i32> for MontyField31<FP>

fn from_int(int: i32) -> Self

Convert a given i32 integer into an element of the MontyField31 field.

fn from_canonical_checked(int: i32) -> Option<Self>

Convert a given i32 integer into an element of the MontyField31 field.

Returns None if the given integer does not lie in the range [(1 - P)/2, (P - 1)/2].

unsafe fn from_canonical_unchecked(int: i32) -> Self

Convert a given i32 integer into an element of the MontyField31 field.

Safety

This is always safe as the conversion to monty form can accept any i32.

impl<FP: FieldParameters> QuotientMap<i64> for MontyField31<FP>

fn from_int(int: i64) -> Self

Convert a given i64 integer into an element of the MontyField31 field.

fn from_canonical_checked(int: i64) -> Option<Self>

Convert a given i64 integer into an element of the MontyField31 field.

Returns None if the given integer does not lie in the range [(1 - P)/2, (P - 1)/2].

unsafe fn from_canonical_unchecked(int: i64) -> Self

Convert a given i64 integer into an element of the MontyField31 field.

Safety

This is always safe as the conversion to monty form can accept any i64.

impl<FP: FieldParameters> QuotientMap<i8> for MontyField31<FP>

fn from_int(int: i8) -> Self

Convert a given i8 integer into an element of the MontyField31 field.

Due to the integer type, the input value is always canonical.

fn from_canonical_checked(int: i8) -> Option<Self>

Convert a given i8 integer into an element of the MontyField31 field.

Due to the integer type, the input value is always canonical.

unsafe fn from_canonical_unchecked(int: i8) -> Self

Convert a given i8 integer into an element of the MontyField31 field.

Due to the integer type, the input value is always canonical.

impl<FP: FieldParameters> QuotientMap<u128> for MontyField31<FP>

fn from_int(int: u128) -> Self

Convert a given u128 integer into an element of the MontyField31 field.

fn from_canonical_checked(int: u128) -> Option<Self>

Convert a given u128 integer into an element of the MontyField31 field.

Returns None if the given integer is greater than the Prime.

unsafe fn from_canonical_unchecked(int: u128) -> Self

Convert a given u128 integer into an element of the MontyField31 field.

Safety

The input must be a valid u64 element.

impl<FP: FieldParameters> QuotientMap<u16> for MontyField31<FP>

fn from_int(int: u16) -> Self

Convert a given u16 integer into an element of the MontyField31 field.

Due to the integer type, the input value is always canonical.

fn from_canonical_checked(int: u16) -> Option<Self>

Convert a given u16 integer into an element of the MontyField31 field.

Due to the integer type, the input value is always canonical.

unsafe fn from_canonical_unchecked(int: u16) -> Self

Convert a given u16 integer into an element of the MontyField31 field.

Due to the integer type, the input value is always canonical.

impl<FP: FieldParameters> QuotientMap<u32> for MontyField31<FP>

fn from_int(int: u32) -> Self

Convert a given u32 integer into an element of the MontyField31 field.

fn from_canonical_checked(int: u32) -> Option<Self>

Convert a given u32 integer into an element of the MontyField31 field.

Returns None if the given integer is greater than the Prime.

unsafe fn from_canonical_unchecked(int: u32) -> Self

Convert a given u32 integer into an element of the MontyField31 field.

Safety

This is always safe as the conversion to monty form can accept any u32.

impl<FP: FieldParameters> QuotientMap<u64> for MontyField31<FP>

fn from_int(int: u64) -> Self

Convert a given u64 integer into an element of the MontyField31 field.

fn from_canonical_checked(int: u64) -> Option<Self>

Convert a given u64 integer into an element of the MontyField31 field.

Returns None if the given integer is greater than the Prime.

unsafe fn from_canonical_unchecked(int: u64) -> Self

Convert a given u64 integer into an element of the MontyField31 field.

Safety

This is always safe as the conversion to monty form can accept any u64.

impl<FP: FieldParameters> QuotientMap<u8> for MontyField31<FP>

fn from_int(int: u8) -> Self

Convert a given u8 integer into an element of the MontyField31 field.

Due to the integer type, the input value is always canonical.

fn from_canonical_checked(int: u8) -> Option<Self>

Convert a given u8 integer into an element of the MontyField31 field.

Due to the integer type, the input value is always canonical.

unsafe fn from_canonical_unchecked(int: u8) -> Self

Convert a given u8 integer into an element of the MontyField31 field.

Due to the integer type, the input value is always canonical.

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

const NUM_BYTES: usize = 4usize

The number of bytes which this field element occupies in memory. Must be equal to the length of self.into_bytes().

fn into_bytes(self) -> [u8; 4]

Convert a field element into a collection of bytes.

fn into_u32_stream( input: impl IntoIterator<Item = Self>, ) -> impl IntoIterator<Item = u32>

Convert an iterator of field elements into an iterator of u32s.

fn into_u64_stream( input: impl IntoIterator<Item = Self>, ) -> impl IntoIterator<Item = u64>

Convert an iterator of field elements into an iterator of u64s.

fn into_parallel_byte_streams<const N: usize>( input: impl IntoIterator<Item = [Self; N]>, ) -> impl IntoIterator<Item = [u8; N]>

Convert an iterator of field element arrays into an iterator of byte arrays.

fn into_parallel_u32_streams<const N: usize>( input: impl IntoIterator<Item = [Self; N]>, ) -> impl IntoIterator<Item = [u32; N]>

Convert an iterator of field element arrays into an iterator of u32 arrays.

fn into_parallel_u64_streams<const N: usize>( input: impl IntoIterator<Item = [Self; N]>, ) -> impl IntoIterator<Item = [u64; N]>

Convert an iterator of field element arrays into an iterator of u64 arrays.

fn into_byte_stream( input: impl IntoIterator<Item = Self>, ) -> impl IntoIterator<Item = u8>

Convert an iterator of field elements into an iterator of bytes.

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<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<MP: MontyParameters, T: Into<Self>> SubAssign<T> for MontyField31<MP>

fn sub_assign(&mut self, rhs: T)

Performs the -= operation.

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 transposes 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>>>

The matrix type used to store the result of a batched DFT operation.

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) of vec.

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

Compute the “coset DFT” of vec.

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

Compute the “coset DFT” of each column in mat.

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 is the inverse operation of “coset DFT”.

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

Compute the “coset iDFT” of each column in mat. This is the inverse operation of “coset DFT”.

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 of vec onto a coset of a larger subgroup.

fn dft_algebra<V>(&self, vec: Vec<V>) -> Vec<V>

where V: BasedVectorSpace<F> + Clone + Send + Sync,

Compute the discrete Fourier transform (DFT) of vec.

fn dft_algebra_batch<V>(&self, mat: DenseMatrix<V>) -> DenseMatrix<V>

where V: BasedVectorSpace<F> + Clone + Send + Sync,

Compute the discrete Fourier transform (DFT) of each column in mat.

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

where V: BasedVectorSpace<F> + Clone + Send + Sync,

Compute the “coset DFT” of vec.

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

where V: BasedVectorSpace<F> + Clone + Send + Sync,

Compute the “coset DFT” of each column in mat.

fn idft_algebra<V>(&self, vec: Vec<V>) -> Vec<V>

where V: BasedVectorSpace<F> + Clone + Send + Sync,

Compute the inverse DFT of vec.

fn idft_algebra_batch<V>(&self, mat: DenseMatrix<V>) -> DenseMatrix<V>

where V: BasedVectorSpace<F> + Clone + Send + Sync,

Compute the inverse DFT of each column in mat.

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

where V: BasedVectorSpace<F> + Clone + Send + Sync,

Compute the “coset iDFT” of vec. This is the inverse operation of “coset DFT”.

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

where V: BasedVectorSpace<F> + Clone + Send + Sync,

Compute the “coset iDFT” of each column in mat. This is the inverse operation of “coset DFT”.

fn lde_algebra<V>(&self, vec: Vec<V>, added_bits: usize) -> Vec<V>

where V: BasedVectorSpace<F> + Clone + Send + Sync,

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

fn lde_algebra_batch<V>( &self, mat: DenseMatrix<V>, added_bits: usize, ) -> DenseMatrix<V>

where V: BasedVectorSpace<F> + Clone + Send + Sync,

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

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

where V: BasedVectorSpace<F> + Clone + Send + Sync,

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

fn coset_lde_algebra_batch<V>( &self, mat: DenseMatrix<V>, added_bits: usize, shift: F, ) -> DenseMatrix<V>

where V: BasedVectorSpace<F> + Clone + Send + Sync,

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<MP: MontyParameters> Packable for MontyField31<MP>

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