Trait ark_ff::fields::Field

pub trait Field: 'static + Copy + Clone + Debug + Display + Default + Send + Sync + Eq + Zero + One + Ord + Neg<Output = Self> + UniformRand + Zeroize + Sized + Hash + CanonicalSerialize + CanonicalSerializeWithFlags + CanonicalDeserialize + CanonicalDeserializeWithFlags + Add<Self, Output = Self> + Sub<Self, Output = Self> + Mul<Self, Output = Self> + Div<Self, Output = Self> + AddAssign<Self> + SubAssign<Self> + MulAssign<Self> + DivAssign<Self> + for<'a> Add<&'a Self, Output = Self> + for<'a> Sub<&'a Self, Output = Self> + for<'a> Mul<&'a Self, Output = Self> + for<'a> Div<&'a Self, Output = Self> + for<'a> AddAssign<&'a Self> + for<'a> SubAssign<&'a Self> + for<'a> MulAssign<&'a Self> + for<'a> DivAssign<&'a Self> + for<'a> Add<&'a mut Self, Output = Self> + for<'a> Sub<&'a mut Self, Output = Self> + for<'a> Mul<&'a mut Self, Output = Self> + for<'a> Div<&'a mut Self, Output = Self> + for<'a> AddAssign<&'a mut Self> + for<'a> SubAssign<&'a mut Self> + for<'a> MulAssign<&'a mut Self> + for<'a> DivAssign<&'a mut Self> + Sum<Self> + for<'a> Sum<&'a Self> + Product<Self> + for<'a> Product<&'a Self> + From<u128> + From<u64> + From<u32> + From<u16> + From<u8> + From<bool> {
    type BasePrimeField: PrimeField;
    type BasePrimeFieldIter: Iterator<Item = Self::BasePrimeField>;

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

    // Required methods
    fn extension_degree() -> u64;
    fn to_base_prime_field_elements(&self) -> Self::BasePrimeFieldIter;
    fn from_base_prime_field_elems(
        elems: &[Self::BasePrimeField]
    ) -> Option<Self>;
    fn from_base_prime_field(elem: Self::BasePrimeField) -> Self;
    fn double(&self) -> Self;
    fn double_in_place(&mut self) -> &mut Self;
    fn neg_in_place(&mut self) -> &mut Self;
    fn from_random_bytes_with_flags<F: Flags>(bytes: &[u8]) -> Option<(Self, F)>;
    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);

    // 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: AsRef<[u64]>>(&self, exp: S) -> Self { ... }
    fn pow_with_table<S: AsRef<[u64]>>(
        powers_of_2: &[Self],
        exp: S
    ) -> Option<Self> { ... }
}

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::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::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 Types

type BasePrimeField: PrimeField

type BasePrimeFieldIter: Iterator<Item = Self::BasePrimeField>

Required Associated Constants

const SQRT_PRECOMP: Option<SqrtPrecomputation<Self>>

Determines the algorithm for computing square roots.

const ZERO: Self

The additive identity of the field.

const ONE: Self

The multiplicative identity of the field.

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) -> Self::BasePrimeFieldIter

fn from_base_prime_field_elems(elems: &[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 double(&self) -> Self

Returns self + self.

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

Doubles self in place.

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

Negates self in place.

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

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.

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: AsRef<[u64]>>(&self, exp: S) -> Self

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

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

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.

Object Safety

This trait is not object safe.

Implementors

impl<P: CubicExtConfig> Field for CubicExtField<P>

type BasePrimeField = <P as CubicExtConfig>::BasePrimeField

type BasePrimeFieldIter = Chain<<<P as CubicExtConfig>::BaseField as Field>::BasePrimeFieldIter, Chain<<<P as CubicExtConfig>::BaseField as Field>::BasePrimeFieldIter, <<P as CubicExtConfig>::BaseField as Field>::BasePrimeFieldIter>>

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

const ZERO: Self = _

const ONE: Self = _

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

type BasePrimeField = Fp<P, N>

type BasePrimeFieldIter = Once<<Fp<P, N> as Field>::BasePrimeField>

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

const ZERO: Self = P::ZERO

const ONE: Self = P::ONE

impl<P: QuadExtConfig> Field for QuadExtField<P>

type BasePrimeField = <P as QuadExtConfig>::BasePrimeField

type BasePrimeFieldIter = Chain<<<P as QuadExtConfig>::BaseField as Field>::BasePrimeFieldIter, <<P as QuadExtConfig>::BaseField as Field>::BasePrimeFieldIter>

const SQRT_PRECOMP: Option<SqrtPrecomputation<Self>> = None

const ZERO: Self = _

const ONE: Self = _