Struct risc0_zkp::field::baby_bear::Elem

#[repr(transparent)]
pub struct Elem(_);

The BabyBear 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 Elem

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

Create a new BabyBear from a raw integer.

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

pub const fn as_u32_montgomery(&self) -> u32

Return the Montgomery form representation used for byte-based hashes of slices of BabyBears.

Trait Implementations

impl Add<Elem> for Elem

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

Addition for Baby Bear Elem

type Output = Elem

The resulting type after applying the + operator.

impl AddAssign<Elem> for Elem

fn add_assign(&mut self, rhs: Self)

Simple addition case for Baby Bear Elem

impl Clone for Elem

fn clone(&self) -> Elem

Returns a copy of the value.

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

Performs copy-assignment from source.

impl Debug for Elem

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

Formats the value using the given formatter.

impl Default for Elem

fn default() -> Self

Returns the “default value” for a type.

impl Elem for Elem

fn inv(self) -> Self

Compute the multiplicative inverse of x, or 1 / x in finite field terms. Since we know by Fermat’s Little Theorem that x ^ (P - 1) == 1 % P for any x != 0, it follows that x * x ^ (P - 2) == 1 % P for x != 0. That is, x ^ (P - 2) is the multiplicative inverse of x. Note that if computed this way, the inverse of zero comes out as zero, which we allow because it is convenient in many cases.

fn random(rng: &mut impl RngCore) -> Self

Generate a random value within the Baby Bear field

const INVALID: Self = _

Invalid, a value that is not a member of the field. This should only be used with the “is_valid” or “unwrap_or_zero” methods.

const ZERO: Self = _

Zero, the additive identity.

const ONE: Self = _

One, the multiplicative identity.

const WORDS: usize = 1usize

How many u32 words are required to hold a single element

fn from_u64(val: u64) -> Self

Import a number into the field from the natural numbers.

fn to_u32_words(&self) -> Vec<u32>

Represent a field element as a sequence of u32s

fn from_u32_words(val: &[u32]) -> Self

Interpret a sequence of u32s as a field element

fn is_valid(&self) -> bool

Returns true if this element is not INVALID. Unlike most methods, this may be called on an INVALID element.

fn pow(self, exp: usize) -> Self

Return an element raised to the given power.

fn valid_or_zero(&self) -> Self

Returns 0 if this element is INVALID, else the value of this element. Unlike most methods, this may be called on an INVALID element.

fn ensure_valid(&self) -> &Self

Returns this element, but checks to make sure it’s valid.

fn as_u32_slice(elems: &[Self]) -> &[u32]

Interprets a slice of these elements as u32s. These elements may not be INVALID.

fn as_u32_slice_unchecked(elems: &[Self]) -> &[u32]

Interprets a slice of these elements as u32s. These elements may potentially be INVALID.

fn from_u32_slice(u32s: &[u32]) -> &[Self]

Interprets a slice of u32s as a slice of these elements. These elements may not be INVALID.

fn from_u32_slice_unchecked(u32s: &[u32]) -> &[Self]

Interprets a slice of u32s as a slice of these elements. These elements may be INVALID.

impl From<&Elem> for u32

fn from(x: &Elem) -> Self

Converts to this type from the input type.

impl From<Elem> for ExtElem

fn from(x: Elem) -> Self

Converts to this type from the input type.

impl From<Elem> for u32

fn from(x: Elem) -> Self

Converts to this type from the input type.

impl From<Elem> for u64

fn from(x: Elem) -> Self

Converts to this type from the input type.

impl From<u32> for Elem

fn from(x: u32) -> Self

Converts to this type from the input type.

impl From<u64> for Elem

fn from(x: u64) -> Self

Converts to this type from the input type.

impl Mul<Elem> for Elem

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

Multiplication for Baby Bear Elem

type Output = Elem

The resulting type after applying the * operator.

impl Mul<Elem> for ExtElem

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

Multiplication by a Baby Bear Elem

type Output = ExtElem

The resulting type after applying the * operator.

impl Mul<ExtElem> for Elem

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

Multiplication for a subfield Elem by an ExtElem

type Output = ExtElem

The resulting type after applying the * operator.

impl MulAssign<Elem> for Elem

fn mul_assign(&mut self, rhs: Self)

Simple multiplication case for Baby Bear Elem

impl MulAssign<Elem> for ExtElem

fn mul_assign(&mut self, rhs: Elem)

Simple multiplication case by a Baby Bear Elem

impl Neg for Elem

type Output = Elem

The resulting type after applying the - operator.

fn neg(self) -> Self

Performs the unary - operation.

impl Ord for Elem

fn cmp(&self, rhs: &Self) -> Ordering

This method returns an Ordering between self and other.

fn max(self, other: Self) -> Selfwhere
    Self: Sized,

Compares and returns the maximum of two values.

fn min(self, other: Self) -> Selfwhere
    Self: Sized,

Compares and returns the minimum of two values.

fn clamp(self, min: Self, max: Self) -> Selfwhere
    Self: Sized + PartialOrd<Self>,

Restrict a value to a certain interval.

impl PartialEq<Elem> for Elem

fn eq(&self, rhs: &Self) -> bool

This method tests for self and other values to be equal, and is used by ==.

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

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

impl PartialOrd<Elem> for Elem

fn partial_cmp(&self, rhs: &Self) -> Option<Ordering>

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

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

This method tests less than (for self and other) and is used by the < operator.

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

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

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

This method tests greater than (for self and other) and is used by the > operator.

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

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

impl RootsOfUnity for Elem

const MAX_ROU_PO2: usize = 27usize

Maximum power of two for which we have a root of unity using Baby Bear field

const ROU_FWD: &'static [Elem] = _

‘Forward’ root of unity for each power of two.

const ROU_REV: &'static [Elem] = _

‘Reverse’ root of unity for each power of two.

impl Sub<Elem> for Elem

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

Subtraction for Baby Bear Elem

type Output = Elem

The resulting type after applying the - operator.

impl SubAssign<Elem> for Elem

fn sub_assign(&mut self, rhs: Self)

Simple subtraction case for Baby Bear Elem

impl Zeroable for Elem

fn zeroed() -> Self

Calls zeroed.

impl Copy for Elem

impl Eq for Elem

impl Pod for Elem

impl Send for Elem

impl StructuralEq for Elem

impl Sync for Elem