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;
Show 20 methods
// 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]> { ... }
}
Expand description
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§
Sourceconst SQRT_PRECOMP: Option<SqrtPrecomputation<Self>>
const SQRT_PRECOMP: Option<SqrtPrecomputation<Self>>
Determines the algorithm for computing square roots.
Required Associated Types§
Required Methods§
Sourcefn extension_degree() -> u64
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>
Sourcefn from_base_prime_field_elems(
elems: impl IntoIterator<Item = Self::BasePrimeField>,
) -> Option<Self>
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.
Sourcefn from_base_prime_field(elem: Self::BasePrimeField) -> Self
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());
Sourcefn from_random_bytes_with_flags<F>(bytes: &[u8]) -> Option<(Self, F)>where
F: Flags,
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.
Sourcefn legendre(&self) -> LegendreSymbol
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
Sourcefn square_in_place(&mut self) -> &mut Self
fn square_in_place(&mut self) -> &mut Self
Squares self
in place.
Sourcefn inverse(&self) -> Option<Self>
fn inverse(&self) -> Option<Self>
Computes the multiplicative inverse of self
if self
is nonzero.
Sourcefn inverse_in_place(&mut self) -> Option<&mut Self>
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()
.
Sourcefn frobenius_map_in_place(&mut self, power: usize)
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§
Sourcefn characteristic() -> &'static [u64]
fn characteristic() -> &'static [u64]
Returns the characteristic of the field, in little-endian representation.
Sourcefn from_random_bytes(bytes: &[u8]) -> Option<Self>
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.
Sourcefn sqrt_in_place(&mut self) -> Option<&mut Self>
fn sqrt_in_place(&mut self) -> Option<&mut Self>
Sets self
to be the square root of self
, if it exists.
Sourcefn sum_of_products<const T: usize>(a: &[Self; T], b: &[Self; T]) -> Self
fn sum_of_products<const T: usize>(a: &[Self; T], b: &[Self; T]) -> Self
Returns sum([a_i * b_i])
.
Sourcefn frobenius_map(&self, power: usize) -> Self
fn frobenius_map(&self, power: usize) -> Self
Returns self^s
, where s = Self::BasePrimeField::MODULUS^power
.
This is also called the Frobenius automorphism.
Sourcefn pow<S>(&self, exp: S) -> Self
fn pow<S>(&self, exp: S) -> Self
Returns self^exp
, where exp
is an integer represented with u64
limbs,
least significant limb first.
Sourcefn pow_with_table<S>(powers_of_2: &[Self], exp: S) -> Option<Self>
fn pow_with_table<S>(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.
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.