Struct Mersenne31 

pub struct Mersenne31 { /* private fields */ }

The prime field F_p where p = 2^31 - 1.

Implementations

impl Mersenne31

pub const EXT_TWO_ADIC_GENERATORS: [[Self; 2]; 33]

Precomputed table of generators for two-adic subgroups of the degree two extension field over Mersenne31. The i’th element is a generator of the subgroup of order 2^i.

pub const fn new_checked(value: u32) -> Option<Self>

Convert a u32 element into a Mersenne31 element.

Panics

This will panic if the element does not lie in the range: [0, 2^31 - 1].

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. This allows inputs to be > 2^31, and just reduces them mod P.

This means that this will be slower than array.map(Mersenne31::new_checked) but has the advantage of being able to be used in const environments.

Trait Implementations

impl Add for Mersenne31

type Output = Mersenne31

The resulting type after applying the + operator.

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

Performs the + operation.

impl<T: Into<Self>> AddAssign<T> for Mersenne31

fn add_assign(&mut self, rhs: T)

Performs the += operation.

impl BinomiallyExtendable<3> for Mersenne31

const W: Self

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

const DTH_ROOT: Self

A D-th root of unity derived from W.

const EXT_GENERATOR: [Self; 3]

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

impl BinomiallyExtendableAlgebra<Mersenne31, 3> for Mersenne31

fn binomial_mul(a: &[Self; D], b: &[Self; D], res: &mut [Self; D], w: F)

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

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

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

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

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

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

impl Clone for Mersenne31

fn clone(&self) -> Mersenne31

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl ComplexExtendable for Mersenne31

const CIRCLE_TWO_ADICITY: usize = 31usize

The two-adicity of p+1, the order of the circle group.

const COMPLEX_GENERATOR: Complex<Self>

fn circle_two_adic_generator(bits: usize) -> Complex<Self>

impl Debug for Mersenne31

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

Formats the value using the given formatter.

impl Default for Mersenne31

fn default() -> Mersenne31

Returns the “default value” for a type.

impl<'a> Deserialize<'a> for Mersenne31

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

Deserialize this value from the given Serde deserializer.

impl Display for Mersenne31

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

Formats the value using the given formatter.

impl Distribution<Mersenne31> for StandardUniform

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

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 Div for Mersenne31

type Output = Mersenne31

The resulting type after applying the / operator.

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

Performs the / operation.

impl DivAssign for Mersenne31

fn div_assign(&mut self, rhs: Mersenne31)

Performs the /= operation.

impl<const WIDTH: usize> ExternalLayer<Mersenne31, WIDTH, MERSENNE31_S_BOX_DEGREE> for Poseidon2ExternalLayerMersenne31<WIDTH>

fn permute_state_initial(&self, state: &mut [Mersenne31; WIDTH])

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

fn permute_state_terminal(&self, state: &mut [Mersenne31; WIDTH])

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

impl<const WIDTH: usize> ExternalLayerConstructor<Mersenne31, WIDTH> for Poseidon2ExternalLayerMersenne31<WIDTH>

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

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

impl Field for Mersenne31

const GENERATOR: Self

A generator of this field’s multiplicative group.

type Packing = Mersenne31

fn is_zero(&self) -> bool

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

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_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 HasComplexBinomialExtension<2> for Mersenne31

const W: Complex<Self>

const DTH_ROOT: Complex<Self>

const EXT_GENERATOR: [Complex<Self>; 2]

impl HasComplexBinomialExtension<3> for Mersenne31

const W: Complex<Self>

const DTH_ROOT: Complex<Self>

const EXT_GENERATOR: [Complex<Self>; 3]

impl HasTwoAdicBinomialExtension<2> for Mersenne31

const EXT_TWO_ADICITY: usize = 32usize

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

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

Returns a two-adic generator for the extension field.

impl HasTwoAdicComplexBinomialExtension<2> for Mersenne31

const COMPLEX_EXT_TWO_ADICITY: usize = 33usize

fn complex_ext_two_adic_generator(bits: usize) -> [Complex<Self>; 2]

impl HasTwoAdicComplexBinomialExtension<3> for Mersenne31

const COMPLEX_EXT_TWO_ADICITY: usize = 32usize

fn complex_ext_two_adic_generator(bits: usize) -> [Complex<Self>; 3]

impl Hash for Mersenne31

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 InjectiveMonomial<5> for Mersenne31

fn injective_exp_n(&self) -> Self

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

impl InternalLayer<Mersenne31, 16, MERSENNE31_S_BOX_DEGREE> for Poseidon2InternalLayerMersenne31

fn permute_state(&self, state: &mut [Mersenne31; 16])

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

impl InternalLayer<Mersenne31, 24, MERSENNE31_S_BOX_DEGREE> for Poseidon2InternalLayerMersenne31

fn permute_state(&self, state: &mut [Mersenne31; 24])

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

impl InternalLayerConstructor<Mersenne31> for Poseidon2InternalLayerMersenne31

fn new_from_constants(internal_constants: Vec<Mersenne31>) -> Self

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

impl Mul for Mersenne31

type Output = Mersenne31

The resulting type after applying the * operator.

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

Performs the * operation.

impl<T: Into<Self>> MulAssign<T> for Mersenne31

fn mul_assign(&mut self, rhs: T)

Performs the *= operation.

impl Neg for Mersenne31

type Output = Mersenne31

The resulting type after applying the - operator.

fn neg(self) -> Self::Output

Performs the unary - operation.

impl Ord for Mersenne31

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 PartialEq for Mersenne31

fn eq(&self, other: &Self) -> 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 PartialOrd for Mersenne31

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 PermutationMonomial<5> for Mersenne31

fn injective_exp_root_n(&self) -> Self

In the field Mersenne31, a^{1/5} is equal to a^{1717986917}.

This follows from the calculation 5 * 1717986917 = 4*(2^31 - 2) + 1 = 1 mod p - 1.

impl PrimeCharacteristicRing for Mersenne31

const ZERO: Self

The additive identity of the ring.

const ONE: Self

The multiplicative identity of the ring.

const TWO: Self

The element in the ring given by ONE + ONE.

const NEG_ONE: Self

The element in the ring given by -ONE.

type PrimeSubfield = Mersenne31

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

fn from_prime_subfield(f: Self::PrimeSubfield) -> Self

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

fn from_bool(b: bool) -> Self

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

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 sum_array<const N: usize>(input: &[Self]) -> Self

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

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

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

Compute the dot product of two vectors.

impl PrimeField for Mersenne31

fn as_canonical_biguint(&self) -> BigUint

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

impl PrimeField32 for Mersenne31

const ORDER_U32: u32 = 2_147_483_647u32

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 PrimeField64 for Mersenne31

const ORDER_U64: u64 = 2_147_483_647u64

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 Product for Mersenne31

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

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

impl QuotientMap<i128> for Mersenne31

fn from_int(int: i128) -> Mersenne31

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

This checks the sign and then makes use of the equivalent method for unsigned integers. This should be avoided in performance critical locations.

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

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

Returns None if the input does not lie in the range:[-2^30, 2^30].

unsafe fn from_canonical_unchecked(int: i128) -> Mersenne31

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

Safety

The input must lie in the range:[1 - 2^31, 2^31 - 1].

impl QuotientMap<i16> for Mersenne31

fn from_int(int: i16) -> Self

Convert a given i16 integer into an element of the Mersenne31 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 Mersenne31 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 Mersenne31 field.

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

impl QuotientMap<i32> for Mersenne31

fn from_int(int: i32) -> Self

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

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

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

Returns none if the input does not lie in the range (-2^30, 2^30).

unsafe fn from_canonical_unchecked(int: i32) -> Self

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

Safety

The input must lie in the range: [1 - 2^31, 2^31 - 1].

impl QuotientMap<i64> for Mersenne31

fn from_int(int: i64) -> Mersenne31

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

This checks the sign and then makes use of the equivalent method for unsigned integers. This should be avoided in performance critical locations.

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

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

Returns None if the input does not lie in the range:[-2^30, 2^30].

unsafe fn from_canonical_unchecked(int: i64) -> Mersenne31

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

Safety

The input must lie in the range:[1 - 2^31, 2^31 - 1].

impl QuotientMap<i8> for Mersenne31

fn from_int(int: i8) -> Self

Convert a given i8 integer into an element of the Mersenne31 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 Mersenne31 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 Mersenne31 field.

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

impl QuotientMap<u128> for Mersenne31

fn from_int(int: u128) -> Mersenne31

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

Uses a modular reduction to reduce to canonical form. This should be avoided in performance critical locations.

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

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

Returns None if the input does not lie in the range:[0, 2^31 - 2].

unsafe fn from_canonical_unchecked(int: u128) -> Mersenne31

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

Safety

The input must lie in the range:[0, 2^31 - 1].

impl QuotientMap<u16> for Mersenne31

fn from_int(int: u16) -> Self

Convert a given u16 integer into an element of the Mersenne31 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 Mersenne31 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 Mersenne31 field.

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

impl QuotientMap<u32> for Mersenne31

fn from_int(int: u32) -> Self

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

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

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

Returns none if the input does not lie in the range [0, 2^31 - 1].

unsafe fn from_canonical_unchecked(int: u32) -> Self

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

Safety

The input must lie in the range: [0, 2^31 - 1].

impl QuotientMap<u64> for Mersenne31

fn from_int(int: u64) -> Mersenne31

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

Uses a modular reduction to reduce to canonical form. This should be avoided in performance critical locations.

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

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

Returns None if the input does not lie in the range:[0, 2^31 - 2].

unsafe fn from_canonical_unchecked(int: u64) -> Mersenne31

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

Safety

The input must lie in the range:[0, 2^31 - 1].

impl QuotientMap<u8> for Mersenne31

fn from_int(int: u8) -> Self

Convert a given u8 integer into an element of the Mersenne31 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 Mersenne31 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 Mersenne31 field.

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

impl RawDataSerializable for Mersenne31

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 Serialize for Mersenne31

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

Serialize this value into the given Serde serializer.

impl Sub for Mersenne31

type Output = Mersenne31

The resulting type after applying the - operator.

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

Performs the - operation.

impl<T: Into<Self>> SubAssign<T> for Mersenne31

fn sub_assign(&mut self, rhs: T)

Performs the -= operation.

impl Sum for Mersenne31

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

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

impl Copy for Mersenne31

impl Eq for Mersenne31

impl MdsPermutation<Mersenne31, 12> for MdsMatrixMersenne31

impl MdsPermutation<Mersenne31, 16> for MdsMatrixMersenne31

impl MdsPermutation<Mersenne31, 32> for MdsMatrixMersenne31

impl MdsPermutation<Mersenne31, 64> for MdsMatrixMersenne31

impl MdsPermutation<Mersenne31, 8> for MdsMatrixMersenne31

impl Packable for Mersenne31