Struct Fp

pub struct Fp(/* private fields */);

The Fp class is an element of the finite field F_p, where P is the prime number 15*2^27 + 1. Put another way, Fp is basically integer arithmetic modulo P.

The Fp datatype is the core type of all of the operations done within the zero knowledge proofs, and is the smallest ‘addressable’ datatype, and the base type of which all composite types are built. In many ways, one can imagine it as the word size of a very strange architecture.

This specific prime P was chosen to:

• Be less than 2^31 so that it fits within a 32 bit word and doesn’t overflow on addition.
• Otherwise have as large a power of 2 in the factors of P-1 as possible.

This last property is useful for number theoretical transforms (the fast fourier transform equivelant on finite fields). See NTT.h for details.

The Fp class wraps all the standard arithmetic operations to make the finite field elements look basically like ordinary numbers (which they mostly are).

Implementations

impl Fp

pub const fn new(x: u32) -> Self

Create a new Fp from a raw integer.

pub fn max() -> Self

Return the maximum value that an Fp can take.

pub fn pow(self, n: usize) -> Self

Raise an Fp value to the power of n.

pub fn inv(self) -> Self

Compute the multiplicative inverse of x, or 1 / x in finite field terms. Since x ^ (P - 1) == 1 % P for any x != 0 (as a consequence of Fermat’s little theorem), it follows that x * x ^ (P - 2) == 1 % P for x != 0. That is, x ^ (P - 2) is the multiplicative inverse of x. Computed this way, the inverse of zero comes out as zero, which is convenient in many cases, so we leave it.

Trait Implementations

impl Add for Fp

type Output = Fp

The resulting type after applying the + operator.

fn add(self, rhs: Self) -> Self

Performs the + operation.

impl AddAssign for Fp

fn add_assign(&mut self, rhs: Self)

Performs the += operation.

impl Clone for Fp

fn clone(&self) -> Fp

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl Debug for Fp

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl Default for Fp

fn default() -> Fp

Returns the “default value” for a type.

impl FpMul for Fp

fn fp_mul(self, x: Fp) -> Self

Multiply self by a factor of Fp type.

impl From<&Fp> for u32

fn from(x: &Fp) -> Self

Converts to this type from the input type.

impl From<Fp> for Fp4

fn from(x: Fp) -> Self

Converts to this type from the input type.

impl From<Fp> for u32

fn from(x: Fp) -> Self

Converts to this type from the input type.

impl From<Fp> for u64

fn from(x: Fp) -> Self

Converts to this type from the input type.

impl From<u32> for Fp

fn from(x: u32) -> Self

Converts to this type from the input type.

impl From<u64> for Fp

fn from(x: u64) -> Self

Converts to this type from the input type.

impl Mul<Fp> for Fp4

type Output = Fp4

The resulting type after applying the * operator.

fn mul(self, rhs: Fp) -> Self

Performs the * operation.

impl Mul<Fp4> for Fp

type Output = Fp4

The resulting type after applying the * operator.

fn mul(self, rhs: Fp4) -> Fp4

Performs the * operation.

impl Mul for Fp

type Output = Fp

The resulting type after applying the * operator.

fn mul(self, rhs: Self) -> Self

Performs the * operation.

impl MulAssign<Fp> for Fp4

Implement the simple multiplication case by the subfield Fp.

fn mul_assign(&mut self, rhs: Fp)

Performs the *= operation.

impl MulAssign for Fp

fn mul_assign(&mut self, rhs: Self)

Performs the *= operation.

impl Neg for Fp

type Output = Fp

The resulting type after applying the - operator.

fn neg(self) -> Self

Performs the unary - operation.

impl PartialEq for Fp

fn eq(&self, other: &Fp) -> bool

Tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Rhs) -> bool

Tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl PartialOrd for Fp

fn partial_cmp(&self, other: &Fp) -> Option<Ordering>

This method returns an ordering between self and other values if one exists.

fn lt(&self, other: &Rhs) -> bool

Tests less than (for self and other) and is used by the < operator.

fn le(&self, other: &Rhs) -> bool

Tests less than or equal to (for self and other) and is used by the <= operator.

fn gt(&self, other: &Rhs) -> bool

Tests greater than (for self and other) and is used by the > operator.

fn ge(&self, other: &Rhs) -> bool

Tests greater than or equal to (for self and other) and is used by the >= operator.

impl Random for Fp

fn random<R: Rng>(rng: &mut R) -> Self

Generate a uniform random value.

impl Sub for Fp

type Output = Fp

The resulting type after applying the - operator.

fn sub(self, rhs: Self) -> Self

Performs the - operation.

impl SubAssign for Fp

fn sub_assign(&mut self, rhs: Self)

Performs the -= operation.

impl Zeroable for Fp

fn zeroed() -> Self

Calls zeroed.

impl Copy for Fp

impl Eq for Fp

impl Pod for Fp

impl StructuralPartialEq for Fp