Trait Field

pub trait Field:
    Sized
    + 'static
    + Copy
    + Clone
    + Debug
    + Display
    + Default
    + Send
    + Sync
    + Eq
    + Zero
    + One
    + Ord
    + Neg<Output = Self>
    + UniformRand
    + Zeroize
    + Hash
    + CanonicalSerialize
    + CanonicalSerializeWithFlags
    + CanonicalDeserialize
    + CanonicalDeserializeWithFlags
    + AdditiveGroup<Scalar = Self>
    + Div<Output = Self, Output = Self, Output = Self>
    + DivAssign
    + for<'a> Div<&'a Self>
    + for<'a> DivAssign<&'a Self>
    + for<'a> Div<&'a mut Self>
    + for<'a> DivAssign<&'a mut Self>
    + for<'a> Product<&'a Self>
    + From<u128>
    + From<u64>
    + From<u32>
    + From<u16>
    + From<u8>
    + From<i128>
    + From<i64>
    + From<i32>
    + From<i16>
    + From<i8>
    + From<bool>
    + Product {
    type BasePrimeField: PrimeField;

    const SQRT_PRECOMP: Option<SqrtPrecomputation<Self>>;
    const ONE: Self;

    // Required methods
    fn extension_degree() -> u64;
    fn to_base_prime_field_elements(
        &self,
    ) -> impl Iterator<Item = Self::BasePrimeField>;
    fn from_base_prime_field_elems(
        elems: impl IntoIterator<Item = Self::BasePrimeField>,
    ) -> Option<Self>;
    fn from_base_prime_field(elem: Self::BasePrimeField) -> Self;
    fn from_random_bytes_with_flags<F>(bytes: &[u8]) -> Option<(Self, F)>
       where F: Flags;
    fn legendre(&self) -> LegendreSymbol;
    fn square(&self) -> Self;
    fn square_in_place(&mut self) -> &mut Self;
    fn inverse(&self) -> Option<Self>;
    fn inverse_in_place(&mut self) -> Option<&mut Self>;
    fn frobenius_map_in_place(&mut self, power: usize);
    fn mul_by_base_prime_field(&self, elem: &Self::BasePrimeField) -> Self;

    // Provided methods
    fn characteristic() -> &'static [u64] { ... }
    fn from_random_bytes(bytes: &[u8]) -> Option<Self> { ... }
    fn sqrt(&self) -> Option<Self> { ... }
    fn sqrt_in_place(&mut self) -> Option<&mut Self> { ... }
    fn sum_of_products<const T: usize>(a: &[Self; T], b: &[Self; T]) -> Self { ... }
    fn frobenius_map(&self, power: usize) -> Self { ... }
    fn pow<S>(&self, exp: S) -> Self
       where S: AsRef<[u64]> { ... }
    fn pow_with_table<S>(powers_of_2: &[Self], exp: S) -> Option<Self>
       where S: AsRef<[u64]> { ... }
}

The interface for a generic field. Types implementing Field support common field operations such as addition, subtraction, multiplication, and inverses.

Defining your own field

To demonstrate the various field operations, we can first define a prime ordered field $\mathbb{F}_{p}$ with $p = 17$. When defining a field $\mathbb{F}_p$, we need to provide the modulus(the $p$ in $\mathbb{F}_p$) and a generator. Recall that a generator $g \in \mathbb{F}_p$ is a field element whose powers comprise the entire field: $\mathbb{F}_p =\{g, g^1, \ldots, g^{p-1}\}$. We can then manually construct the field element associated with an integer with Fp::from and perform field addition, subtraction, multiplication, and inversion on it.

use ark_ff::{AdditiveGroup, fields::{Field, Fp64, MontBackend, MontConfig}};

#[derive(MontConfig)]
#[modulus = "17"]
#[generator = "3"]
pub struct FqConfig;
pub type Fq = Fp64<MontBackend<FqConfig, 1>>;

let a = Fq::from(9);
let b = Fq::from(10);

assert_eq!(a, Fq::from(26));          // 26 =  9 mod 17
assert_eq!(a - b, Fq::from(16));      // -1 = 16 mod 17
assert_eq!(a + b, Fq::from(2));       // 19 =  2 mod 17
assert_eq!(a * b, Fq::from(5));       // 90 =  5 mod 17
assert_eq!(a.square(), Fq::from(13)); // 81 = 13 mod 17
assert_eq!(b.double(), Fq::from(3));  // 20 =  3 mod 17
assert_eq!(a / b, a * b.inverse().unwrap()); // need to unwrap since `b` could be 0 which is not invertible

Using pre-defined fields

In the following example, we’ll use the field associated with the BLS12-381 pairing-friendly group.

use ark_ff::{AdditiveGroup, Field};
use ark_test_curves::bls12_381::Fq as F;
use ark_std::{One, UniformRand, test_rng};

let mut rng = test_rng();
// Let's sample uniformly random field elements:
let a = F::rand(&mut rng);
let b = F::rand(&mut rng);

let c = a + b;
let d = a - b;
assert_eq!(c + d, a.double());

let e = c * d;
assert_eq!(e, a.square() - b.square());         // (a + b)(a - b) = a^2 - b^2
assert_eq!(a.inverse().unwrap() * a, F::one()); // Euler-Fermat theorem tells us: a * a^{-1} = 1 mod p

Required Associated Constants

const SQRT_PRECOMP: Option<SqrtPrecomputation<Self>>

Determines the algorithm for computing square roots.

const ONE: Self

The multiplicative identity of the field.

Required Associated Types

type BasePrimeField: PrimeField

Required Methods

fn extension_degree() -> u64

Returns the extension degree of this field with respect to Self::BasePrimeField.

fn to_base_prime_field_elements( &self, ) -> impl Iterator<Item = Self::BasePrimeField>

fn from_base_prime_field_elems( elems: impl IntoIterator<Item = Self::BasePrimeField>, ) -> Option<Self>

Convert a slice of base prime field elements into a field element. If the slice length != Self::extension_degree(), must return None.

fn from_base_prime_field(elem: Self::BasePrimeField) -> Self

Constructs a field element from a single base prime field elements.

assert_eq!(F2::from_base_prime_field(F::one()), F2::one());

fn from_random_bytes_with_flags<F>(bytes: &[u8]) -> Option<(Self, F)>

where F: Flags,

Attempt to deserialize a field element, splitting the bitflags metadata according to F specification. Returns None if the deserialization fails.

This function is primarily intended for sampling random field elements from a hash-function or RNG output.

fn legendre(&self) -> LegendreSymbol

Returns a LegendreSymbol, which indicates whether this field element is 1 : a quadratic residue 0 : equal to 0 -1 : a quadratic non-residue

fn square(&self) -> Self

Returns self * self.

fn square_in_place(&mut self) -> &mut Self

Squares self in place.

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

Computes the multiplicative inverse of self if self is nonzero.

fn inverse_in_place(&mut self) -> Option<&mut Self>

If self.inverse().is_none(), this just returns None. Otherwise, it sets self to self.inverse().unwrap().

fn frobenius_map_in_place(&mut self, power: usize)

Sets self to self^s, where s = Self::BasePrimeField::MODULUS^power. This is also called the Frobenius automorphism.

fn mul_by_base_prime_field(&self, elem: &Self::BasePrimeField) -> Self

Provided Methods

fn characteristic() -> &'static [u64]

Returns the characteristic of the field, in little-endian representation.

fn from_random_bytes(bytes: &[u8]) -> Option<Self>

Attempt to deserialize a field element. Returns None if the deserialization fails.

This function is primarily intended for sampling random field elements from a hash-function or RNG output.

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

Returns the square root of self, if it exists.

fn sqrt_in_place(&mut self) -> Option<&mut Self>

Sets self to be the square root of self, if it exists.

fn sum_of_products<const T: usize>(a: &[Self; T], b: &[Self; T]) -> Self

Returns sum([a_i * b_i]).

fn frobenius_map(&self, power: usize) -> Self

Returns self^s, where s = Self::BasePrimeField::MODULUS^power. This is also called the Frobenius automorphism.

fn pow<S>(&self, exp: S) -> Self

where S: AsRef<[u64]>,

Returns self^exp, where exp is an integer represented with u64 limbs, least significant limb first.

fn pow_with_table<S>(powers_of_2: &[Self], exp: S) -> Option<Self>

where S: AsRef<[u64]>,

Exponentiates a field element f by a number represented with u64 limbs, using a precomputed table containing as many powers of 2 of f as the 1 + the floor of log2 of the exponent exp, starting from the 1st power. That is, powers_of_2 should equal &[p, p^2, p^4, ..., p^(2^n)] when exp has at most n bits.

This returns None when a power is missing from the table.

Dyn Compatibility

This trait is not dyn compatible.

In older versions of Rust, dyn compatibility was called "object safety", so this trait is not object safe.

Implementors

impl<P> Field for CubicExtField<P>

where P: CubicExtConfig,

const SQRT_PRECOMP: Option<SqrtPrecomputation<CubicExtField<P>>> = P::SQRT_PRECOMP

const ONE: CubicExtField<P> = _

type BasePrimeField = <P as CubicExtConfig>::BasePrimeField

impl<P> Field for QuadExtField<P>

where P: QuadExtConfig,

const SQRT_PRECOMP: Option<SqrtPrecomputation<QuadExtField<P>>> = None

const ONE: QuadExtField<P> = _

type BasePrimeField = <P as QuadExtConfig>::BasePrimeField

impl<P, const N: usize> Field for Fp<P, N>

where P: FpConfig<N>,

const SQRT_PRECOMP: Option<SqrtPrecomputation<Fp<P, N>>> = P::SQRT_PRECOMP

const ONE: Fp<P, N> = P::ONE

type BasePrimeField = Fp<P, N>