Trait scuttlebutt::field::FiniteField

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

    const GENERATOR: Self;

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

    // Provided methods
    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 { ... }
}

Types that implement this trait are finite fields.

Required Associated Types

type PrimeField: PrimeFiniteField + IsSubFieldOf<Self>

The prime-order subfield of the finite field.

type NumberOfBitsInBitDecomposition: ArrayLength<bool> + ArrayLength<F2>

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

const GENERATOR: Self

The generator for the multiplicative group.

Required Methods

fn polynomial_modulus() -> Polynomial<Self::PrimeField>

Multiplication over field elements should be reduced over this polynomial.

fn bit_decomposition( &self ) -> GenericArray<bool, Self::NumberOfBitsInBitDecomposition>

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.

fn inverse(&self) -> Self

Compute the multiplicative inverse of self.

Panics

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

Provided Methods

fn decompose<T: FiniteField + IsSubFieldOf<Self>>( &self ) -> GenericArray<T, DegreeModulo<T, Self>>

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

See IsSubFieldOf for more info.

fn from_subfield<T: FiniteField + IsSubFieldOf<Self>>( arr: &GenericArray<T, DegreeModulo<T, Self>> ) -> Self

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

See IsSubFieldOf for more info.

Object Safety

This trait is not object safe.

Implementors

impl FiniteField for F2

type PrimeField = F2

const GENERATOR: Self = _

type NumberOfBitsInBitDecomposition = UInt<UTerm, B1>

impl FiniteField for F40b

type PrimeField = F2

const GENERATOR: Self = _

type NumberOfBitsInBitDecomposition = UInt<UInt<UInt<UInt<UInt<UInt<UTerm, B1>, B0>, B1>, B0>, B0>, B0>

impl FiniteField for F45b

type PrimeField = F2

const GENERATOR: Self = _

type NumberOfBitsInBitDecomposition = UInt<UInt<UInt<UInt<UInt<UInt<UTerm, B1>, B0>, B1>, B1>, B0>, B1>

impl FiniteField for F56b

type PrimeField = F2

const GENERATOR: Self = _

type NumberOfBitsInBitDecomposition = UInt<UInt<UInt<UInt<UInt<UInt<UTerm, B1>, B1>, B1>, B0>, B0>, B0>

impl FiniteField for F61p

type PrimeField = F61p

const GENERATOR: Self = _

type NumberOfBitsInBitDecomposition = UInt<UInt<UInt<UInt<UInt<UInt<UTerm, B1>, B1>, B1>, B1>, B0>, B1>

impl FiniteField for F63b

type PrimeField = F2

const GENERATOR: Self = _

type NumberOfBitsInBitDecomposition = UInt<UInt<UInt<UInt<UInt<UInt<UTerm, B1>, B1>, B1>, B1>, B1>, B1>

impl FiniteField for F64b

type PrimeField = F2

type NumberOfBitsInBitDecomposition = UInt<UInt<UInt<UInt<UInt<UInt<UInt<UTerm, B1>, B0>, B0>, B0>, B0>, B0>, B0>

const GENERATOR: Self = _

impl FiniteField for F128b

type PrimeField = F2

const GENERATOR: Self = _

type NumberOfBitsInBitDecomposition = UInt<UInt<UInt<UInt<UInt<UInt<UInt<UInt<UTerm, B1>, B0>, B0>, B0>, B0>, B0>, B0>, B0>