Trait scuttlebutt::field::FiniteField

source · [−]
pub trait FiniteField: FiniteRing + DivAssign<Self> + Div<Self, Output = Self> {
    type PrimeField: PrimeFiniteField + IsSubFieldOf<Self>;
    type NumberOfBitsInBitDecomposition: ArrayLength<bool> + ArrayLength<F2>;

    const GENERATOR: Self;

    fn polynomial_modulus() -> Polynomial<Self::PrimeField>;
    fn bit_decomposition(
        &self
    ) -> GenericArray<bool, Self::NumberOfBitsInBitDecomposition>;
    fn inverse(&self) -> Self;

    fn decompose<T: FiniteField + IsSubFieldOf<Self>>(
        &self
    ) -> GenericArray<T, DegreeModulo<T, Self>> { ... }
    fn from_subfield<T: FiniteField + IsSubFieldOf<Self>>(
        arr: &GenericArray<T, DegreeModulo<T, Self>>
    ) -> Self { ... }
}
Expand description

Types that implement this trait are finite fields.

Required Associated Types

The prime-order subfield of the finite field.

The number of bits in the bit decomposition of any element of this finite field.

This number should be equal to (for the field $\textsf{GF}(p^r)$):

\lceil\log_2(p)\rceil \cdot r

See Self::bit_decomposition for the exact meaning of bit decomposition

Required Associated Constants

The generator for the multiplicative group.

Required Methods

Multiplication over field elements should be reduced over this polynomial.

Decompose the given field element into bits.

This bit decomposition should be done according to Weng et al., section 5.

Let $p$ be a positive prime. Let $r$ be a positive integer. Let $m=\lceil\log_2 p\rceil$, the number of bits needed to represent $p$.

Let $F = \textsf{GF}(p^r)$ be the current field (the field represented by Self).

Let $v$ be a vector of $r \cdot m$ elements of $F$. Let $v = (v_0, v_1, \ldots, v_{rm}) \in F^{rm}$. We define (don’t worry about $g$, we’re just keeping the syntax of the paper) $\langle g,v\rangle \in F$ using the polynomial representation of F, below:

\langle g, v \rangle(x) \coloneqq
\sum\limits_{i=0}^{r-1} \left( x^i \cdot \sum\limits_{j=1}^{m-1}
2^j \cdot v_{i \cdot m + j}
\right )

Let $f \in F$. Let $b \in \{0,1\}^{rm} \subseteq F^{rm}$ (that is, a 0/1 vector where 0/1 are field elements of $F$), such that $\langle g, b \rangle = f$.

Invoking the bit_decomposition function on f should yield the vector $b$ where a 0 element of $b$ corresponds to false and a 1 element corresponds to true.

Compute the multiplicative inverse of self.

Panics

This function will panic if *self == Self::ZERO

Provided Methods

Decompose self into an array of T elements where T is a subfield of Self.

See IsSubFieldOf for more info.

Create a field element from an array of subfield T elements.

See IsSubFieldOf for more info.

Implementors