Struct BinomialExtensionField 

pub struct BinomialExtensionField<F, const D: usize, A = F> { /* private fields */ }

Implementations

impl<F, A, const D: usize> BinomialExtensionField<F, D, A>

pub const fn new(value: [A; D]) -> BinomialExtensionField<F, D, A>

Create an extension field element from an array of base elements.

Any array is accepted. No reduction is required since base elements are already valid field elements.

impl<F, const D: usize> BinomialExtensionField<F, D>

where F: Copy,

pub const fn new_array<const N: usize>( input: [[F; D]; N], ) -> [BinomialExtensionField<F, D>; N]

Convert a [[F; D]; N] array to an array of extension field elements.

Const version of input.map(BinomialExtensionField::new).

Panics

Panics if N == 0.

impl<R> BinomialExtensionField<R, 2>

where R: PrimeCharacteristicRing,

Convenience methods for complex extensions

pub const fn new_complex(real: R, imag: R) -> BinomialExtensionField<R, 2>

pub const fn new_real(real: R) -> BinomialExtensionField<R, 2>

pub const fn new_imag(imag: R) -> BinomialExtensionField<R, 2>

pub fn real(&self) -> R

pub fn imag(&self) -> R

pub fn conjugate(&self) -> BinomialExtensionField<R, 2>

pub fn norm(&self) -> R

pub fn to_array(&self) -> [R; 2]

pub fn rotate<Ext>( &self, rhs: &BinomialExtensionField<Ext, 2>, ) -> BinomialExtensionField<Ext, 2>

where Ext: Algebra<R>,

Trait Implementations

impl<F, A, const D: usize> Add<A> for BinomialExtensionField<F, D, A>

where F: BinomiallyExtendable<D>, A: Algebra<F>,

type Output = BinomialExtensionField<F, D, A>

The resulting type after applying the + operator.

fn add(self, rhs: A) -> BinomialExtensionField<F, D, A>

Performs the + operation.

impl<F, A, const D: usize> Add for BinomialExtensionField<F, D, A>

where F: BinomiallyExtendable<D>, A: BinomiallyExtendableAlgebra<F, D>,

type Output = BinomialExtensionField<F, D, A>

The resulting type after applying the + operator.

fn add( self, rhs: BinomialExtensionField<F, D, A>, ) -> BinomialExtensionField<F, D, A>

Performs the + operation.

impl<F, A, const D: usize> AddAssign<A> for BinomialExtensionField<F, D, A>

where F: BinomiallyExtendable<D>, A: Algebra<F>,

fn add_assign(&mut self, rhs: A)

Performs the += operation.

impl<F, A, const D: usize> AddAssign for BinomialExtensionField<F, D, A>

where F: BinomiallyExtendable<D>, A: Algebra<F>,

fn add_assign(&mut self, rhs: BinomialExtensionField<F, D, A>)

Performs the += operation.

impl<F, A, const D: usize> BasedVectorSpace<A> for BinomialExtensionField<F, D, A>

where F: BinomiallyExtendable<D>, A: Algebra<F>,

const DIMENSION: usize = D

The dimension of the vector space, i.e. the number of elements in its basis.

fn as_basis_coefficients_slice(&self) -> &[A]

Fixes a basis for the algebra A and uses this to map an element of A to a slice of DIMENSION F elements.

fn from_basis_coefficients_fn<Fn>(f: Fn) -> BinomialExtensionField<F, D, A>

where Fn: FnMut(usize) -> A,

Fixes a basis for the algebra A and uses this to map DIMENSION F elements to an element of A. Similar to core:array::from_fn, the DIMENSION F elements are given by Fn(0), ..., Fn(DIMENSION - 1) called in that order.

fn from_basis_coefficients_iter<I>( iter: I, ) -> Option<BinomialExtensionField<F, D, A>>

where I: ExactSizeIterator<Item = A>,

Fixes a basis for the algebra A and uses this to map DIMENSION F elements to an element of A.

fn flatten_to_base(vec: Vec<BinomialExtensionField<F, D, A>>) -> Vec<A>

Convert from a vector of Self to a vector of F by flattening the basis coefficients.

fn reconstitute_from_base(vec: Vec<A>) -> Vec<BinomialExtensionField<F, D, A>>

Convert from a vector of F to a vector of Self by combining the basis coefficients.

fn from_basis_coefficients_slice(slice: &[F]) -> Option<Self>

Fixes a basis for the algebra A and uses this to map DIMENSION F elements to an element of A.

fn ith_basis_element(i: usize) -> Option<Self>

Given a basis for the Algebra A, return the i’th basis element.

impl<F, const D: usize> BinomiallyExtendable<D> for BinomialExtensionField<F, 2>

where F: HasComplexBinomialExtension<D>,

const W: BinomialExtensionField<F, 2>

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

const DTH_ROOT: BinomialExtensionField<F, 2>

A D-th root of unity derived from W.

const EXT_GENERATOR: [BinomialExtensionField<F, 2>; D] = F::EXT_GENERATOR

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

impl<F, const D: usize> BinomiallyExtendableAlgebra<BinomialExtensionField<F, 2>, D> for BinomialExtensionField<F, 2>

where F: HasComplexBinomialExtension<D>,

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<F, const D: usize, A> Clone for BinomialExtensionField<F, D, A>

where F: Clone, A: Clone,

fn clone(&self) -> BinomialExtensionField<F, D, A>

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl<F, const D: usize, A> Debug for BinomialExtensionField<F, D, A>

where F: Debug, A: Debug,

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

Formats the value using the given formatter.

impl<F, A, const D: usize> Default for BinomialExtensionField<F, D, A>

where F: Field, A: Algebra<F>,

fn default() -> BinomialExtensionField<F, D, A>

Returns the “default value” for a type.

impl<'de, F, const D: usize, A> Deserialize<'de> for BinomialExtensionField<F, D, A>

where A: Deserialize<'de>,

fn deserialize<__D>( __deserializer: __D, ) -> Result<BinomialExtensionField<F, D, A>, <__D as Deserializer<'de>>::Error>

where __D: Deserializer<'de>,

Deserialize this value from the given Serde deserializer.

impl<F, const D: usize> Display for BinomialExtensionField<F, D>

where F: BinomiallyExtendable<D>,

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

Formats the value using the given formatter.

impl<F, const D: usize> Div for BinomialExtensionField<F, D>

where F: BinomiallyExtendable<D>,

type Output = BinomialExtensionField<F, D>

The resulting type after applying the / operator.

fn div( self, rhs: BinomialExtensionField<F, D>, ) -> <BinomialExtensionField<F, D> as Div>::Output

Performs the / operation.

impl<F, const D: usize> DivAssign for BinomialExtensionField<F, D>

where F: BinomiallyExtendable<D>,

fn div_assign(&mut self, rhs: BinomialExtensionField<F, D>)

Performs the /= operation.

impl<F, const D: usize> ExtensionField<F> for BinomialExtensionField<F, D>

where F: BinomiallyExtendable<D>,

type ExtensionPacking = PackedBinomialExtensionField<F, <F as Field>::Packing, D>

fn is_in_basefield(&self) -> bool

Determine if the given element lies in the base field.

fn as_base(&self) -> Option<F>

If the element lies in the base field project it down. Otherwise return None.

impl<F, const D: usize> Field for BinomialExtensionField<F, D>

where F: BinomiallyExtendable<D>,

const GENERATOR: BinomialExtensionField<F, D>

A generator of this field’s multiplicative group.

type Packing = BinomialExtensionField<F, D>

fn try_inverse(&self) -> Option<BinomialExtensionField<F, D>>

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

fn add_slices( slice_1: &mut [BinomialExtensionField<F, D>], slice_2: &[BinomialExtensionField<F, D>], )

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

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 bits() -> usize

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

impl<F, A, const D: usize> From<[A; D]> for BinomialExtensionField<F, D, A>

where F: Field, A: Algebra<F>,

fn from(x: [A; D]) -> BinomialExtensionField<F, D, A>

Converts to this type from the input type.

impl<F, A, const D: usize> From<A> for BinomialExtensionField<F, D, A>

where F: Field, A: Algebra<F>,

fn from(x: A) -> BinomialExtensionField<F, D, A>

Converts to this type from the input type.

impl<F, const D: usize> HasFrobenius<F> for BinomialExtensionField<F, D>

where F: BinomiallyExtendable<D>,

fn frobenius(&self) -> BinomialExtensionField<F, D>

FrobeniusField automorphisms: x -> x^n, where n is the order of BaseField.

fn repeated_frobenius(&self, count: usize) -> BinomialExtensionField<F, D>

Repeated Frobenius automorphisms: x -> x^(n^count).

Follows precomputation suggestion in Section 11.3.3 of the Handbook of Elliptic and Hyperelliptic Curve Cryptography.

fn pseudo_inv(&self) -> BinomialExtensionField<F, D>

Compute the pseudo inverse of a given element making use of the Frobenius automorphism.

Returns 0 if self == 0, and 1/self otherwise.

Algorithm 11.3.4 in Handbook of Elliptic and Hyperelliptic Curve Cryptography.

fn galois_orbit(self) -> Vec<Self>

Returns the full Galois orbit of the element under Frobenius.

impl<F, const D: usize> HasTwoAdicBinomialExtension<D> for BinomialExtensionField<F, 2>

where F: HasTwoAdicComplexBinomialExtension<D>,

const EXT_TWO_ADICITY: usize = F::COMPLEX_EXT_TWO_ADICITY

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

fn ext_two_adic_generator(bits: usize) -> [BinomialExtensionField<F, 2>; D]

Returns a two-adic generator for the extension field.

impl<F, const D: usize, A> Hash for BinomialExtensionField<F, D, A>

where F: Hash, A: Hash,

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<F, A, const D: usize> Mul<A> for BinomialExtensionField<F, D, A>

where F: BinomiallyExtendable<D>, A: BinomiallyExtendableAlgebra<F, D>,

type Output = BinomialExtensionField<F, D, A>

The resulting type after applying the * operator.

fn mul(self, rhs: A) -> BinomialExtensionField<F, D, A>

Performs the * operation.

impl<F, A, const D: usize> Mul for BinomialExtensionField<F, D, A>

where F: BinomiallyExtendable<D>, A: BinomiallyExtendableAlgebra<F, D>,

type Output = BinomialExtensionField<F, D, A>

The resulting type after applying the * operator.

fn mul( self, rhs: BinomialExtensionField<F, D, A>, ) -> BinomialExtensionField<F, D, A>

Performs the * operation.

impl<F, A, const D: usize> MulAssign<A> for BinomialExtensionField<F, D, A>

where F: BinomiallyExtendable<D>, A: BinomiallyExtendableAlgebra<F, D>,

fn mul_assign(&mut self, rhs: A)

Performs the *= operation.

impl<F, A, const D: usize> MulAssign for BinomialExtensionField<F, D, A>

where F: BinomiallyExtendable<D>, A: BinomiallyExtendableAlgebra<F, D>,

fn mul_assign(&mut self, rhs: BinomialExtensionField<F, D, A>)

Performs the *= operation.

impl<F, A, const D: usize> Neg for BinomialExtensionField<F, D, A>

where F: BinomiallyExtendable<D>, A: Algebra<F>,

type Output = BinomialExtensionField<F, D, A>

The resulting type after applying the - operator.

fn neg(self) -> BinomialExtensionField<F, D, A>

Performs the unary - operation.

impl<F, const D: usize, A> Ord for BinomialExtensionField<F, D, A>

where F: Ord, A: Ord,

fn cmp(&self, other: &BinomialExtensionField<F, D, A>) -> 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<F, const D: usize, A> PartialEq for BinomialExtensionField<F, D, A>

where F: PartialEq, A: PartialEq,

fn eq(&self, other: &BinomialExtensionField<F, D, A>) -> 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<F, const D: usize, A> PartialOrd for BinomialExtensionField<F, D, A>

where F: PartialOrd, A: PartialOrd,

fn partial_cmp( &self, other: &BinomialExtensionField<F, D, A>, ) -> 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<F, A, const D: usize> PrimeCharacteristicRing for BinomialExtensionField<F, D, A>

where F: BinomiallyExtendable<D>, A: BinomiallyExtendableAlgebra<F, D>,

const ZERO: BinomialExtensionField<F, D, A>

The additive identity of the ring.

const ONE: BinomialExtensionField<F, D, A>

The multiplicative identity of the ring.

const TWO: BinomialExtensionField<F, D, A>

The element in the ring given by ONE + ONE.

const NEG_ONE: BinomialExtensionField<F, D, A>

The element in the ring given by -ONE.

type PrimeSubfield = <A as PrimeCharacteristicRing>::PrimeSubfield

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

fn from_prime_subfield( f: <BinomialExtensionField<F, D, A> as PrimeCharacteristicRing>::PrimeSubfield, ) -> BinomialExtensionField<F, D, A>

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

fn halve(&self) -> BinomialExtensionField<F, D, A>

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

fn square(&self) -> BinomialExtensionField<F, D, A>

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

fn mul_2exp_u64(&self, exp: u64) -> BinomialExtensionField<F, D, A>

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

fn div_2exp_u64(&self, exp: u64) -> BinomialExtensionField<F, D, A>

Divide by a given power of two. div_2exp_u64(a, exp) = a/2^exp

fn zero_vec(len: usize) -> Vec<BinomialExtensionField<F, D, A>>

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

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 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 * (x - 1).

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.

fn sum_array<const N: usize>(input: &[Self]) -> Self

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

impl<F, A, const D: usize> Product for BinomialExtensionField<F, D, A>

where F: BinomiallyExtendable<D>, A: BinomiallyExtendableAlgebra<F, D>,

fn product<I>(iter: I) -> BinomialExtensionField<F, D, A>

where I: Iterator<Item = BinomialExtensionField<F, D, A>>,

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

impl<F, const D: usize> RawDataSerializable for BinomialExtensionField<F, D>

where F: BinomiallyExtendable<D>,

const NUM_BYTES: usize

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) -> impl IntoIterator<Item = u8>

Convert a field element into a collection of bytes.

fn into_byte_stream( input: impl IntoIterator<Item = BinomialExtensionField<F, D>>, ) -> impl IntoIterator<Item = u8>

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

fn into_u32_stream( input: impl IntoIterator<Item = BinomialExtensionField<F, D>>, ) -> impl IntoIterator<Item = u32>

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

fn into_u64_stream( input: impl IntoIterator<Item = BinomialExtensionField<F, D>>, ) -> 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 = [BinomialExtensionField<F, D>; 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 = [BinomialExtensionField<F, D>; 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 = [BinomialExtensionField<F, D>; N]>, ) -> impl IntoIterator<Item = [u64; N]>

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

impl<F, const D: usize, A> Serialize for BinomialExtensionField<F, D, A>

where A: Serialize,

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<F, A, const D: usize> Sub<A> for BinomialExtensionField<F, D, A>

where F: BinomiallyExtendable<D>, A: Algebra<F>,

type Output = BinomialExtensionField<F, D, A>

The resulting type after applying the - operator.

fn sub(self, rhs: A) -> BinomialExtensionField<F, D, A>

Performs the - operation.

impl<F, A, const D: usize> Sub for BinomialExtensionField<F, D, A>

where F: BinomiallyExtendable<D>, A: BinomiallyExtendableAlgebra<F, D>,

type Output = BinomialExtensionField<F, D, A>

The resulting type after applying the - operator.

fn sub( self, rhs: BinomialExtensionField<F, D, A>, ) -> BinomialExtensionField<F, D, A>

Performs the - operation.

impl<F, A, const D: usize> SubAssign<A> for BinomialExtensionField<F, D, A>

where F: BinomiallyExtendable<D>, A: Algebra<F>,

fn sub_assign(&mut self, rhs: A)

Performs the -= operation.

impl<F, A, const D: usize> SubAssign for BinomialExtensionField<F, D, A>

where F: BinomiallyExtendable<D>, A: Algebra<F>,

fn sub_assign(&mut self, rhs: BinomialExtensionField<F, D, A>)

Performs the -= operation.

impl<F, A, const D: usize> Sum for BinomialExtensionField<F, D, A>

where F: BinomiallyExtendable<D>, A: BinomiallyExtendableAlgebra<F, D>,

fn sum<I>(iter: I) -> BinomialExtensionField<F, D, A>

where I: Iterator<Item = BinomialExtensionField<F, D, A>>,

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

impl<F, const D: usize> TwoAdicField for BinomialExtensionField<F, D>

where F: Field + HasTwoAdicBinomialExtension<D>,

const TWO_ADICITY: usize = F::EXT_TWO_ADICITY

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

fn two_adic_generator(bits: usize) -> BinomialExtensionField<F, D>

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

impl<F, const D: usize> Algebra<F> for BinomialExtensionField<F, D>

where F: BinomiallyExtendable<D>,

impl<F, const D: usize, A> Copy for BinomialExtensionField<F, D, A>

where F: Copy, A: Copy,

impl<F, const D: usize, A> Eq for BinomialExtensionField<F, D, A>

where F: Eq, A: Eq,

impl<F, const D: usize> Packable for BinomialExtensionField<F, D>

where F: BinomiallyExtendable<D>,

impl<F, const D: usize, A> StructuralPartialEq for BinomialExtensionField<F, D, A>