Trait FieldInternal

Source

pub trait FieldInternal:
    Debug
    + Copy
    + PartialEq
    + Eq
    + Hash
    + Sized
    + MaybeArbitrary<()>
    + 'static {
    type ElementContainer: FieldElementContainer;

Show 25 methods    // Required methods
    fn el(self, value: Self::ElementContainer) -> FieldElement<Self>;
    fn add_assign(self, a: &mut FieldElement<Self>, b: FieldElement<Self>);
    fn mul_assign(self, a: &mut FieldElement<Self>, b: FieldElement<Self>);
    fn neg(self, a: FieldElement<Self>) -> FieldElement<Self>;
    fn inv(self, a: FieldElement<Self>) -> Option<FieldElement<Self>>;
    fn frobenius(self, a: FieldElement<Self>) -> FieldElement<Self>;
    fn encode(self, element: FieldElement<Self>) -> u64;
    fn decode(self, element: u64) -> FieldElement<Self>;
    fn bit_length(self) -> usize;
    fn fma_limb(
        self,
        limb_a: u64,
        limb_b: u64,
        coeff: FieldElement<Self>,
    ) -> u64;
    fn reduce(self, limb: u64) -> u64;

    // Provided methods
    fn sub_assign(self, a: &mut FieldElement<Self>, b: FieldElement<Self>) { ... }
    fn add(
        self,
        a: FieldElement<Self>,
        b: FieldElement<Self>,
    ) -> FieldElement<Self> { ... }
    fn sub(
        self,
        a: FieldElement<Self>,
        b: FieldElement<Self>,
    ) -> FieldElement<Self> { ... }
    fn mul(
        self,
        a: FieldElement<Self>,
        b: FieldElement<Self>,
    ) -> FieldElement<Self> { ... }
    fn div(
        self,
        a: FieldElement<Self>,
        b: FieldElement<Self>,
    ) -> Option<FieldElement<Self>> { ... }
    fn bitmask(self) -> u64 { ... }
    fn entries_per_limb(self) -> usize { ... }
    fn limb_bit_index_pair(self, idx: usize) -> LimbBitIndexPair { ... }
    fn is_reduced(self, limb: u64) -> bool { ... }
    fn pack<T: Iterator<Item = FieldElement<Self>>>(self, entries: T) -> u64 { ... }
    fn unpack(self, limb: u64) -> LimbIterator<Self> ⓘ { ... }
    fn number(self, dim: usize) -> usize { ... }
    fn range(self, start: usize, end: usize) -> Range<usize> { ... }
    fn truncate(self, sum: u64) -> Option<u64> { ... }
}

Expand description

Internal methods required for fields.

A field has several responsibilities. It must define:

what its elements “look like”, i.e. how they are represented in memory;
how to perform finite field operations on those elements, namely addition, subtraction, multiplication, division (except by zero), and the Frobenius endomorphism;
how to pack and unpack elements into and from Limbs, so that FqVector can handle them.

We want a trait that makes all those definitions. However, we don’t want to expose these implementation details to the outside world. Therefore, we define a public trait that defines public field methods (e.g. constructing the zero element) and an internal trait that takes care of the details. The latter trait is FieldInternal.

The fact that each field defines its own element type means that we can define a single struct that packages both a field and one of its elements, and this struct will be how we expose field operations to the outside world.

Required Associated Types§

Source

type ElementContainer: FieldElementContainer

The internal representation of a field element.

Required Methods§

Source

fn el(self, value: Self::ElementContainer) -> FieldElement<Self>

Create a new field element. This is the method responsible for ensuring that the returned value is in a consistent state. For example, for a prime field of characteristic p, this function is responsible for ensuring that the FieldElement that is returned contains a value in the range 0..p.

Source

fn encode(self, element: FieldElement<Self>) -> u64

Encode a field element into a Limb. The limbs of an FqVector<Self> will consist of the coordinates of the vector, packed together using this method. It is assumed that the output value occupies at most self.bit_length() bits with the rest padded with zeros, and that the limb is reduced.

It is required that self.encode(self.zero()) == 0 (whenever Self implements Field).

Source

fn decode(self, element: u64) -> FieldElement<Self>

Decode a Limb into a field element. The argument will always contain a single encoded field element, padded with zeros. This is the inverse of encode.

Source

fn bit_length(self) -> usize

Return the number of bits a Self::Element occupies in a limb.

Source

fn fma_limb(self, limb_a: u64, limb_b: u64, coeff: FieldElement<Self>) -> u64

Fused multiply-add. Return the Limb whose ith entry is limb_a[i] + coeff * limb_b[i]. Both limb_a and limb_b are assumed to be reduced, and the result does not have to be reduced.

Source

fn reduce(self, limb: u64) -> u64

Reduce a limb, i.e. make it “canonical”. For example, in Fp, this replaces every entry by its value modulo p.

Many functions assume that the input limbs are reduced, but it’s useful to allow the existence of non-reduced limbs for performance reasons. Some functions like fma_limb can be very quick compared to the reduction step, so finishing a computation by reducing all limbs in sequence may allow the compiler to play some tricks with, for example, loop unrolling and SIMD.

Provided Methods§

Source

fn sub_assign(self, a: &mut FieldElement<Self>, b: FieldElement<Self>)

Source

fn add(self, a: FieldElement<Self>, b: FieldElement<Self>) -> FieldElement<Self>

Source

fn sub(self, a: FieldElement<Self>, b: FieldElement<Self>) -> FieldElement<Self>

Source

fn mul(self, a: FieldElement<Self>, b: FieldElement<Self>) -> FieldElement<Self>

Source

fn div( self, a: FieldElement<Self>, b: FieldElement<Self>, ) -> Option<FieldElement<Self>>

Source

fn bitmask(self) -> u64

If l is a limb of Self::Elements, then l & F.bitmask() is the value of the first entry of l.

Source

fn entries_per_limb(self) -> usize

The number of Self::Elements that fit in a single limb.

Source

fn limb_bit_index_pair(self, idx: usize) -> LimbBitIndexPair

Source

fn is_reduced(self, limb: u64) -> bool

Check whether or not a limb is reduced. This may potentially not be faster than calling reduce directly.

Source

fn pack<T: Iterator<Item = FieldElement<Self>>>(self, entries: T) -> u64

Given an interator of FieldElement<Self>s, pack all of them into a single limb in order. It is assumed that the values of the iterator fit into a single limb. If this assumption is violated, the result will be nonsense.

Source

fn unpack(self, limb: u64) -> LimbIterator<Self> ⓘ

Give an iterator over the entries of limb.

Source

fn number(self, dim: usize) -> usize

Return the number of limbs required to hold dim entries.

Source

fn range(self, start: usize, end: usize) -> Range<usize>

Return the Range<usize> starting at the index of the limb containing the startth entry, and ending at the index of the limb containing the endth entry (including the latter).

Source