Type Alias BabyBear

pub type BabyBear = MontyField31<BabyBearParameters>;

The prime field 2^31 - 2^27 + 1, a.k.a. the Baby Bear field.

Aliased Type

struct BabyBear { /* private fields */ }

Implementations

impl<MP> MontyField31<MP>

where MP: FieldParameters + TwoAdicData,

pub fn backward_fft( input: &mut [MontyField31<MP>], root_table: &[Vec<MontyField31<MP>>], )

impl<MP> MontyField31<MP>

where MP: FieldParameters + TwoAdicData,

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

impl<MP> MontyField31<MP>

where MP: FieldParameters + TwoAdicData,

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

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.

impl<MP> MontyField31<MP>

where MP: MontyParameters,

pub const fn new(value: u32) -> MontyField31<MP>

pub const fn new_array<const N: usize>(input: [u32; N]) -> [MontyField31<MP>; 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], ) -> [[MontyField31<MP>; 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) -> MontyField31<MP>

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<PMP> Add<PackedMontyField31Neon<PMP>> for MontyField31<PMP>

where PMP: PackedMontyParameters,

type Output = PackedMontyField31Neon<PMP>

The resulting type after applying the + operator.

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

Performs the + operation.

impl<FP> Add for MontyField31<FP>

where FP: MontyParameters,

type Output = MontyField31<FP>

The resulting type after applying the + operator.

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

Performs the + operation.

impl<FP> AddAssign for MontyField31<FP>

where FP: MontyParameters,

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

Performs the += operation.

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

where FP: BinomialExtensionData<WIDTH> + FieldParameters,

const W: MontyField31<FP>

const DTH_ROOT: MontyField31<FP>

const EXT_GENERATOR: [MontyField31<FP>; WIDTH] = FP::EXT_GENERATOR

impl<MP> Clone for MontyField31<MP>

where MP: Clone + MontyParameters,

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> Debug for MontyField31<FP>

where FP: MontyParameters,

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

Formats the value using the given formatter.

impl<MP> Default for MontyField31<MP>

where MP: Default + MontyParameters,

fn default() -> MontyField31<MP>

Returns the “default value” for a type.

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

where FP: FieldParameters,

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

where D: Deserializer<'de>,

Deserialize this value from the given Serde deserializer.

impl<FP> Display for MontyField31<FP>

where FP: MontyParameters,

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

Formats the value using the given formatter.

impl<FP> Div for MontyField31<FP>

where FP: FieldParameters,

type Output = MontyField31<FP>

The resulting type after applying the / operator.

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

Performs the / operation.

impl<FP> Field for MontyField31<FP>

where FP: FieldParameters,

const GENERATOR: MontyField31<FP> = FP::MONTY_GEN

A generator of this field’s entire multiplicative group.

type Packing = PackedMontyField31Neon<FP>

fn exp_u64_generic<FA>(val: FA, power: u64) -> FA

where FA: FieldAlgebra<F = MontyField31<FP>>,

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

fn try_inverse(&self) -> Option<MontyField31<FP>>

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

fn halve(&self) -> MontyField31<FP>

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<FP> FieldAlgebra for MontyField31<FP>

where FP: FieldParameters,

const ZERO: MontyField31<FP> = FP::MONTY_ZERO

The additive identity of the algebra.

const ONE: MontyField31<FP> = FP::MONTY_ONE

The multiplicative identity of the Algebra

const TWO: MontyField31<FP> = FP::MONTY_TWO

The element in the algebra given by ONE + ONE.

const NEG_ONE: MontyField31<FP> = FP::MONTY_NEG_ONE

The element in the algebra given by -ONE.

type F = MontyField31<FP>

fn from_f(f: <MontyField31<FP> as FieldAlgebra>::F) -> MontyField31<FP>

Interpret a field element as a commutative algebra element.

fn from_canonical_u8(n: u8) -> MontyField31<FP>

Convert from a canonical u8.

fn from_canonical_u16(n: u16) -> MontyField31<FP>

Convert from a canonical u16.

fn from_canonical_u32(n: u32) -> MontyField31<FP>

Convert from a canonical u32.

fn from_canonical_u64(n: u64) -> MontyField31<FP>

Convert from a canonical u64.

fn from_canonical_usize(n: usize) -> MontyField31<FP>

Convert from a canonical usize.

fn from_wrapped_u32(n: u32) -> MontyField31<FP>

fn from_wrapped_u64(n: u64) -> MontyField31<FP>

fn mul_2exp_u64(&self, exp: u64) -> MontyField31<FP>

self * 2^exp

fn zero_vec(len: usize) -> Vec<MontyField31<FP>>

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_bool(b: bool) -> Self

Convert from a bool.

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 exp_u64(&self, power: u64) -> Self

Exponentiation by a u64 power.

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

Exponentiation by a constant power.

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

Compute self^{2^power_log} by repeated squaring.

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 powers_packed<P>(&self) -> Powers<P>

where P: PackedField<Scalar = Self>,

Construct an iterator which returns powers of self packed into PackedField elements.

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

where P: PackedField<Scalar = Self>,

Construct an iterator which returns powers of self shifted by start and packed into PackedField elements.

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

Compute the dot product of two vectors.

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

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

const EXT_TWO_ADICITY: usize

fn ext_two_adic_generator(bits: usize) -> [MontyField31<FP>; WIDTH]

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

impl<MP> Hash for MontyField31<MP>

where MP: Hash + MontyParameters,

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

where __H: Hasher,

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<PMP> Mul<PackedMontyField31Neon<PMP>> for MontyField31<PMP>

where PMP: PackedMontyParameters,

type Output = PackedMontyField31Neon<PMP>

The resulting type after applying the * operator.

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

Performs the * operation.

impl<FP> Mul for MontyField31<FP>

where FP: MontyParameters,

type Output = MontyField31<FP>

The resulting type after applying the * operator.

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

Performs the * operation.

impl<FP> MulAssign for MontyField31<FP>

where FP: MontyParameters,

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

Performs the *= operation.

impl<FP> Neg for MontyField31<FP>

where FP: FieldParameters,

type Output = MontyField31<FP>

The resulting type after applying the - operator.

fn neg(self) -> <MontyField31<FP> as Neg>::Output

Performs the unary - operation.

impl<FP> Ord for MontyField31<FP>

where FP: MontyParameters,

fn cmp(&self, other: &MontyField31<FP>) -> 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 for MontyField31<MP>

where MP: PartialEq + MontyParameters,

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> PartialOrd for MontyField31<FP>

where FP: MontyParameters,

fn partial_cmp(&self, other: &MontyField31<FP>) -> 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> PrimeField for MontyField31<FP>

where FP: FieldParameters,

fn as_canonical_biguint(&self) -> BigUint

impl<FP> PrimeField32 for MontyField31<FP>

where FP: FieldParameters,

const ORDER_U32: u32 = FP::PRIME

fn as_canonical_u32(&self) -> u32

Return the representative of value that is less than ORDER_U32.

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> PrimeField64 for MontyField31<FP>

where FP: FieldParameters,

const ORDER_U64: u64

fn as_canonical_u64(&self) -> u64

Return the representative of value that is less than 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> Product for MontyField31<FP>

where FP: FieldParameters,

fn product<I>(iter: I) -> MontyField31<FP>

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

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

impl<FP> Serialize for MontyField31<FP>

where FP: FieldParameters,

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

where S: Serializer,

Serialize this value into the given Serde serializer.

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

where PMP: PackedMontyParameters,

type Output = PackedMontyField31Neon<PMP>

The resulting type after applying the - operator.

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

Performs the - operation.

impl<FP> Sub for MontyField31<FP>

where FP: MontyParameters,

type Output = MontyField31<FP>

The resulting type after applying the - operator.

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

Performs the - operation.

impl<FP> SubAssign for MontyField31<FP>

where FP: MontyParameters,

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

Performs the -= operation.

impl<FP> Sum for MontyField31<FP>

where FP: MontyParameters,

fn sum<I>(iter: I) -> MontyField31<FP>

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

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

impl<FP> TwoAdicField for MontyField31<FP>

where FP: FieldParameters + TwoAdicData,

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) -> MontyField31<FP>

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

impl<MP> Copy for MontyField31<MP>

where MP: Copy + MontyParameters,

impl<MP> Eq for MontyField31<MP>

where MP: Eq + MontyParameters,

impl<FP> Packable for MontyField31<FP>

where FP: FieldParameters,

impl<MP> StructuralPartialEq for MontyField31<MP>

where MP: MontyParameters,