Struct Poly192 

pub struct Poly192(/* private fields */);

GF(2^192), as three coordinates over GF(2^64) in the basis 1, y, y^2.

The defining relation is y^3 = y + 1, which also gives y^4 = y^2 + y.

Everything below reduces with those two rewrites and nothing else.

Implementations

impl Poly192

pub const fn new(coefficients: [Poly64; 3]) -> Self

The element with the given coordinates in the basis 1, y, y^2.

pub const fn coefficients(self) -> [Poly64; 3]

The coordinates of this element in the basis 1, y, y^2.

pub fn invert_or_zero(self) -> Self

The inverse of this element, with zero sent to zero.

Every step runs whatever the operand is, so the cost says nothing about the value.

Trait Implementations

impl Add for Poly192

type Output = Poly192

The resulting type after applying the + operator.

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

Performs the + operation.

impl Add<Gf2> for Poly192

type Output = Poly192

The resulting type after applying the + operator.

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

Performs the + operation.

impl Add<Poly64> for Poly192

type Output = Poly192

The resulting type after applying the + operator.

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

Performs the + operation.

impl Add<Poly192> for Poly64

type Output = Poly192

The resulting type after applying the + operator.

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

Performs the + operation.

impl Add<Poly192> for Gf2

type Output = Poly192

The resulting type after applying the + operator.

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

Performs the + operation.

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

fn add_assign(&mut self, rhs: T)

Performs the += operation.

impl Algebra<Gf2> for Poly192

fn quadratic_extension_square(a: &[Self; 2], w: F) -> [Self; 2]

Square a[0] + a[1] X modulo X^2 - w.

fn mixed_dot_product<const N: usize>(a: &[Self; N], f: &[F; N]) -> Self

where F: Dup,

Dot product between algebra elements and base field scalars.

const BATCHED_LC_CHUNK: usize = 8

Optimal chunk size for batched_linear_combination.

fn batched_linear_combination(values: &[Self], coeffs: &[F]) -> Self

where F: Dup,

Runtime-length linear combination: Σ values[i] * coeffs[i].

impl Algebra<Poly64> for Poly192

fn quadratic_extension_square(a: &[Self; 2], w: F) -> [Self; 2]

Square a[0] + a[1] X modulo X^2 - w.

fn mixed_dot_product<const N: usize>(a: &[Self; N], f: &[F; N]) -> Self

where F: Dup,

Dot product between algebra elements and base field scalars.

const BATCHED_LC_CHUNK: usize = 8

Optimal chunk size for batched_linear_combination.

fn batched_linear_combination(values: &[Self], coeffs: &[F]) -> Self

where F: Dup,

Runtime-length linear combination: Σ values[i] * coeffs[i].

impl AlgebraIdentity<Poly64> for Poly192

fn algebra_id() -> Vec<u8>

Return the stable, unambiguous identifier of the defining relations and basis.

impl BasedVectorSpace<Poly64> for Poly192

fn flatten_to_base(vec: Vec<Self>) -> Vec<Poly64>

A whole vector of elements is one contiguous run of coordinates, so this is a copy.

const DIMENSION: usize = DEGREE

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

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

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<F: FnMut(usize) -> Poly64>(f: F) -> Self

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: ExactSizeIterator<Item = Poly64>>( iter: I, ) -> Option<Self>

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

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.

fn reconstitute_from_base(vec: Vec<F>) -> Vec<Self>

where F: Sync, Self: Send,

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

impl Clone for Poly192

fn clone(&self) -> Self

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl Copy for Poly192

impl Debug for Poly192

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

Formats the value using the given formatter.

impl Default for Poly192

fn default() -> Self

Returns the “default value” for a type.

impl<'de> Deserialize<'de> for Poly192

fn deserialize<__D>(__deserializer: __D) -> Result<Self, __D::Error>

where __D: Deserializer<'de>,

Deserialize this value from the given Serde deserializer.

impl Display for Poly192

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

Formats the value using the given formatter.

impl Distribution<Poly192> for StandardUniform

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

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 Poly192

type Output = Poly192

The resulting type after applying the / operator.

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

Performs the / operation.

impl Div<Poly64> for Poly192

type Output = Poly192

The resulting type after applying the / operator.

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

Performs the / operation.

impl DivAssign for Poly192

fn div_assign(&mut self, rhs: Poly192)

Performs the /= operation.

impl DivAssign<Poly64> for Poly192

fn div_assign(&mut self, rhs: Poly64)

Performs the /= operation.

impl Eq for Poly192

impl ExtensionField<Poly64> for Poly192

type ExtensionPacking = Poly192

fn is_in_basefield(&self) -> bool

Determine if the given element lies in the base field.

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

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

fn from_ext_basis_coefficients(coeffs: &[Self]) -> Option<Self>

Reassemble an element of Self from D = DIMENSION coefficients in Self via Σⱼ basisⱼ · coeffsⱼ. Returns None if coeffs.len() != Self::DIMENSION.

impl Field for Poly192

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

Algorithm

Multiplication by a fixed element is a 3 x 3 matrix over the coefficient field.

Its columns are where that multiplication sends the three basis elements:

    a * 1   = ( a_0,        a_1,        a_2       )
    a * y   = ( a_2,        a_0 + a_2,  a_1       )
    a * y^2 = ( a_1,        a_1 + a_2,  a_0 + a_2 )

The inverse is the first column of that matrix inverted.

The adjugate gives it as the top row of cofactors over the determinant.

The determinant is the norm down to the coefficient field, and it vanishes only at zero.

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

Squaring is a triangular map on the coordinates, so its inverse is one too.

    b_0 = a_0^2,  b_1 = a_2^2,  b_2 = a_1^2 + a_2^2

Reading that backwards costs three coefficient-field square roots and one addition.

fn bits() -> usize

An element of GF(2^n) is exactly n bits wide.

fn interpolation_node(i: usize) -> Self

The enumeration by bit pattern.

The coordinates over GF(2) run through the coefficient fields in order.

An index narrower than 64 bits therefore lands entirely in the first of them.

const GENERATOR: Self

A generator of this field’s multiplicative group.

type Packing = Poly192

fn order() -> BigUint

The number of elements in the field.

const BENEFITS_FROM_LOCKSTEP_EVALUATION: bool = false

Whether evaluating multiple packed vectors of this field in lockstep (to overlap independent dependency chains and hide packed-multiplication latency) is expected to help throughput for this 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 batched_columnwise_dot_product<EF, R, I, const N: usize>( acc: &mut [<EF as ExtensionField<Self>>::ExtensionPacking], items: I, )

where EF: ExtensionField<Self>, R: Iterator<Item = Self::Packing>, I: Iterator<Item = (R, [EF; N])>,

Accumulate acc[c * N + j] += scales[j] * row[c] over a stream of packed rows.

impl From<Gf2> for Poly192

fn from(x: Gf2) -> Self

GF(2) is the prime subfield, embedded as {ZERO, ONE}.

impl From<Poly64> for Poly192

fn from(x: Poly64) -> Self

The coefficient field sits at the constant coordinate.

impl HasFrobenius<Poly64> for Poly192

fn frobenius(&self) -> Self

The map raising to the size of the coefficient field.

It fixes every coefficient and permutes the basis.

The three roots of the modulus are y, y^2 and y^2 + y, so:

    y^(2^64)                 =  y^2
    a_0 + a_1 y + a_2 y^2    ->  a_0 + a_2 y + (a_1 + a_2) y^2

So one application is one addition and a permutation, with no products at all.

fn repeated_frobenius(&self, count: usize) -> Self

Apply the Frobenius automorphism count times.

fn pseudo_inv(&self) -> Self

Computes the pseudo inverse of the given field element.

fn galois_orbit(self) -> Vec<Self>

Returns the full Galois orbit of the element under Frobenius.

impl Hash for Poly192

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 Mul for Poly192

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

Algorithm

Karatsuba over three limbs: six products instead of the schoolbook nine.

    c_i    = a_i b_i
    d_ij   = (a_i + a_j) (b_i + b_j)
    p_1    = d_01 + c_0 + c_1
    p_2    = d_02 + c_0 + c_1 + c_2
    p_3    = d_12 + c_1 + c_2

The unreduced product spans degrees 0 to 4, and the modulus folds the top two down:

    y^3    = y + 1
    y^4    = y^2 + y

type Output = Poly192

The resulting type after applying the * operator.

impl Mul<Gf2> for Poly192

type Output = Poly192

The resulting type after applying the * operator.

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

Performs the * operation.

impl Mul<Poly64> for Poly192

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

Scaling stays inside each coordinate, so it costs three products rather than six.

type Output = Poly192

The resulting type after applying the * operator.

impl Mul<Poly192> for Poly64

type Output = Poly192

The resulting type after applying the * operator.

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

Performs the * operation.

impl Mul<Poly192> for Gf2

type Output = Poly192

The resulting type after applying the * operator.

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

Performs the * operation.

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

fn mul_assign(&mut self, rhs: T)

Performs the *= operation.

impl Neg for Poly192

type Output = Poly192

The resulting type after applying the - operator.

fn neg(self) -> Self

Performs the unary - operation.

impl Ord for Poly192

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.

fn clamp_to<R>(self, range: R) -> Self

where Self: Sized, R: ClampBounds<Self>,

🔬This is a nightly-only experimental API. (clamp_to)

Restrict a value to a certain range.

impl Packable for Poly192

impl PackedFieldExtension<Poly64, Poly192> for Poly192

One element per vector, so every lane index is zero.

fn from_ext_fn(f: impl Fn(usize) -> Self) -> Self

Construct a packed extension by applying f to each lane.

fn from_ext_slice(slice: &[Self]) -> Self

Pack a length-WIDTH slice of extension field elements into one packed extension.

fn extract(&self, lane: usize) -> Self

Extract the extension field element at the given SIMD lane.

fn add_assign_lane(&mut self, lane: usize, value: Self)

Accumulate value into a single SIMD lane, leaving the other W - 1 lanes unchanged.

fn packed_ext_powers(base: Self) -> Powers<Self>

Similar to packed_powers, construct an iterator which returns powers of base packed into PackedFieldExtension elements.

fn pack_ext_columns<const N: usize>(rows: &[[ExtField; N]]) -> [Self; N]

Pack N columns from W rows of extension field elements into N packed extensions.

fn pack_ext_columns_fn<const N: usize>( row_fn: impl Fn(usize) -> [ExtField; N], ) -> [Self; N]

Pack N columns using a closure that produces each row.

fn to_ext_slice(&self, out: &mut [ExtField])

Write all W lanes into the given slice.

fn unpack_ext_into<const N: usize>( packed: &[Self; N], rows: &mut [[ExtField; N]], )

Unpack N packed extensions into W rows of N extension elements.

fn unpack_ext_iter<const N: usize>( packed: [Self; N], ) -> impl Iterator<Item = [ExtField; N]>

Iterator equivalent of PackedFieldExtension::unpack_ext_into.

fn to_ext_iter( iter: impl IntoIterator<Item = Self>, ) -> impl Iterator<Item = ExtField>

Convert an iterator of packed extension field elements to an iterator of extension field elements (flat — one ExtField per lane per packed value).

fn unpack_transpose_into(src: &[Self], dst: &mut [ExtField], src_width: usize)

Unpacks a packed row-major matrix into its scalar transpose, in one pass.

fn packed_ext_powers_capped( base: ExtField, unpacked_len: usize, ) -> impl Iterator<Item = Self>

Similar to packed_ext_powers but only returns unpacked_len powers of base.

impl PartialEq for Poly192

fn eq(&self, other: &Self) -> bool

Equality operator ==.

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

Inequality operator !=.

impl PartialOrd for Poly192

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 PrimeCharacteristicRing for Poly192

fn square(&self) -> Self

Squaring is F_2-linear, so the cross terms vanish and only the fold survives.

    (a_0 + a_1 y + a_2 y^2)^2  = a_0^2 + a_1^2 y^2 + a_2^2 y^4
                               = a_0^2 + a_2^2 y + (a_1^2 + a_2^2) y^2

fn halve(&self) -> Self

Panics

Always panics: 2 is not invertible in characteristic 2.

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

Panics

Always panics: 2 is not invertible in characteristic 2.

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 = Gf2

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

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_prime_subfield(f: Self::PrimeSubfield) -> Self

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

fn double(&self) -> Self

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

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

Computes the arithmetic generalization of boolean xor.

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

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

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 cube(&self) -> Self

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

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

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

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

impl RawDataSerializable for Poly192

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

Convert an iterator of field elements into an iterator 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.

impl Serialize for Poly192

fn serialize<__S>(&self, __serializer: __S) -> Result<__S::Ok, __S::Error>

where __S: Serializer,

Serialize this value into the given Serde serializer.

impl StructuralPartialEq for Poly192

impl Sub for Poly192

type Output = Poly192

The resulting type after applying the - operator.

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

Performs the - operation.

impl Sub<Gf2> for Poly192

type Output = Poly192

The resulting type after applying the - operator.

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

Performs the - operation.

impl Sub<Poly64> for Poly192

type Output = Poly192

The resulting type after applying the - operator.

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

Performs the - operation.

impl Sub<Poly192> for Poly64

type Output = Poly192

The resulting type after applying the - operator.

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

Performs the - operation.

impl Sub<Poly192> for Gf2

type Output = Poly192

The resulting type after applying the - operator.

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

Performs the - operation.

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

fn sub_assign(&mut self, rhs: T)

Performs the -= operation.

impl Sum for Poly192

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

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