Struct BinaryField2 

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

The binary tower field GF(2^2).

A quadratic extension of Gf2 generated by a root X of X² + αX + 1, where α is the generator of the level below over the one beneath it. The low half of the backing integer holds the coefficient of 1, the high half the coefficient of X.

The serde encoding is canonical: every field element has exactly one valid byte representation (see the manual Deserialize impl below). #[serde(transparent)] makes the derived Serialize emit the backing integer itself, which is what that impl reads back.

Implementations

impl BinaryField2

pub fn from_le_bytes(bytes: [u8; 1]) -> Self

Construct a field element from its little-endian byte representation.

Every byte string of the right length is a valid input: from_repr masks any bits above the canonical range.

Trait Implementations

impl Add for BinaryField2

type Output = BinaryField2

The resulting type after applying the + operator.

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

Performs the + operation.

impl Add<BinaryField2> for BinaryField128

type Output = BinaryField128

The resulting type after applying the + operator.

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

Performs the + operation.

impl Add<BinaryField2> for Gf2

type Output = BinaryField2

The resulting type after applying the + operator.

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

Performs the + operation.

impl Add<BinaryField128> for BinaryField2

type Output = BinaryField128

The resulting type after applying the + operator.

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

Performs the + operation.

impl Add<Gf2> for BinaryField2

type Output = BinaryField2

The resulting type after applying the + operator.

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

Performs the + operation.

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

fn add_assign(&mut self, rhs: T)

Performs the += operation.

impl Algebra<BinaryField2> for BinaryField128

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<Gf2> for BinaryField2

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 Clone for BinaryField2

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 BinaryField2

impl Debug for BinaryField2

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

Formats the value using the given formatter.

impl Default for BinaryField2

fn default() -> Self

Returns the “default value” for a type.

impl<'de> Deserialize<'de> for BinaryField2

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

Deserialize this value from the given Serde deserializer.

impl Display for BinaryField2

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

Formats the value using the given formatter.

impl Distribution<BinaryField2> for StandardUniform

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

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 BinaryField2

type Output = BinaryField2

The resulting type after applying the / operator.

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

Performs the / operation.

impl DivAssign for BinaryField2

fn div_assign(&mut self, rhs: BinaryField2)

Performs the /= operation.

impl Eq for BinaryField2

impl Field for BinaryField2

fn interpolation_node(i: usize) -> Self

The enumeration by bit pattern: interpolation_node(i) is the element whose coefficients over GF(2) are the bits of i. It is injective for i < 2^BITS.

Panics

Panics if i >= 2^BITS. from_repr masks, so an out-of-range index would otherwise alias an earlier node in release builds and break an interpolation argument silently; the check is paid once per node at setup, never in a loop.

fn bits() -> usize

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

const GENERATOR: Self

A generator of this field’s multiplicative group.

type Packing = BinaryField2

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

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

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

A square root of this field element, if one exists.

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<BinaryField2> for BinaryField128

fn from(x: BinaryField2) -> Self

GF(4) occupies the low two bits; every other coefficient vanishes.

impl From<Gf2> for BinaryField2

fn from(x: Gf2) -> Self

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

impl HasSubfield<BinaryField2> for BinaryField128

fn as_subfield(&self) -> Option<BinaryField2>

An element lies in GF(4) exactly when no bit above the lowest two is set.

fn all_in_subfield(values: &[Self]) -> bool

The bits above the lowest two, OR-ed across the slice, vanish exactly when every element lies in GF(4).

The fold has no early exit, so the loop has no data-dependent branch.

impl Hash for BinaryField2

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 BinaryField2

type Output = BinaryField2

The resulting type after applying the * operator.

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

Performs the * operation.

impl Mul<BinaryField2> for BinaryField128

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

x·(c0 + c1·X_0) = c0·x + c1·(X_0·x).

Each coefficient of the scalar selects its term through an all-ones or all-zeros mask, so there is no product and no branch on the scalar.

type Output = BinaryField128

The resulting type after applying the * operator.

impl Mul<BinaryField2> for Gf2

type Output = BinaryField2

The resulting type after applying the * operator.

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

Performs the * operation.

impl Mul<BinaryField128> for BinaryField2

type Output = BinaryField128

The resulting type after applying the * operator.

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

Performs the * operation.

impl Mul<Gf2> for BinaryField2

type Output = BinaryField2

The resulting type after applying the * operator.

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

Performs the * operation.

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

fn mul_assign(&mut self, rhs: T)

Performs the *= operation.

impl Neg for BinaryField2

type Output = BinaryField2

The resulting type after applying the - operator.

fn neg(self) -> Self::Output

Performs the unary - operation.

impl Ord for BinaryField2

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 BinaryField2

impl PartialEq for BinaryField2

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

Equality operator ==.

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

Inequality operator !=.

impl PartialOrd for BinaryField2

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 BinaryField2

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.

fn bool_check(&self) -> Self

x·(x - 1) = x² - x = x² + x in characteristic 2, and squaring is a linear map here, so this avoids the tower/polynomial basis changes a general product pays for.

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

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

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 dot_product<const N: usize>(u: &[Self; N], v: &[Self; N]) -> Self

Compute the dot product of two vectors.

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

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 BinaryField2

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) -> [u8; 1]

Convert a field element into a collection of bytes.

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

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

impl Serialize for BinaryField2

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 BinaryField2

impl Sub for BinaryField2

type Output = BinaryField2

The resulting type after applying the - operator.

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

Performs the - operation.

impl Sub<BinaryField2> for BinaryField128

type Output = BinaryField128

The resulting type after applying the - operator.

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

Performs the - operation.

impl Sub<BinaryField2> for Gf2

type Output = BinaryField2

The resulting type after applying the - operator.

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

Performs the - operation.

impl Sub<BinaryField128> for BinaryField2

type Output = BinaryField128

The resulting type after applying the - operator.

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

Performs the - operation.

impl Sub<Gf2> for BinaryField2

type Output = BinaryField2

The resulting type after applying the - operator.

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

Performs the - operation.

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

fn sub_assign(&mut self, rhs: T)

Performs the -= operation.

impl Sum for BinaryField2

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

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

impl TowerLevel for BinaryField2

fn mul_alpha(self) -> Self

X·(c0 + c1·X) = c1 + (c0 + α·c1)·X, using X² = αX + 1.

const LOG_BITS: usize

The k in GF(2^(2^k)).

type Repr = u8

The backing integer of an element.

fn from_repr(r: Self::Repr) -> Self

Build an element from a bit pattern, discarding the bits above 2^LOG_BITS.

fn to_repr(self) -> Self::Repr

The bit pattern of this element, zero above 2^LOG_BITS.

fn from_le_byte_iter(bytes: impl Iterator<Item = u8>) -> Self

Build an element from the next RawDataSerializable::NUM_BYTES bytes of a little-endian byte stream, discarding the bits above 2^LOG_BITS.

fn cantor_basis(i: usize) -> Self

The i-th vector of the Cantor basis of this level.