Struct Goldilocks

pub struct Goldilocks { /* private fields */ }

The prime field known as Goldilocks, defined as F_p where p = 2^64 - 2^32 + 1.

Note that the safety of deriving Serialize and Deserialize relies on the fact that the internal value can be any u64.

Trait Implementations

impl Add for Goldilocks

type Output = Goldilocks

The resulting type after applying the + operator.

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

Performs the + operation.

impl AddAssign for Goldilocks

fn add_assign(&mut self, rhs: Self)

Performs the += operation.

impl BinomiallyExtendable<2> for Goldilocks

const W: Self

const DTH_ROOT: Self

const EXT_GENERATOR: [Self; 2]

impl Clone for Goldilocks

fn clone(&self) -> Goldilocks

Returns a copy of the value.

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

Performs copy-assignment from source.

impl Convolve<Goldilocks, i128, i64, i128> for SmallConvolveGoldilocks

fn read(input: Goldilocks) -> i128

Return the lift of a Goldilocks element, 0 <= input.value <= P < 2^64. We widen immediately, since some valid Goldilocks elements don’t fit in an i64, and since in any case overflow can occur for even the smallest convolutions.

fn parity_dot<const N: usize>(u: [i128; N], v: [i64; N]) -> i128

For a convolution of size N, |x| < N * 2^64 and (as per the assumption above), |y| < 2^51. So the product is at most N * 2^115 which will not overflow for N <= 16. We widen y at this point to perform the multiplication.

fn reduce(z: i128) -> Goldilocks

The assumptions above mean z < N^2 * 2^115, which is at most 2^123 when N <= 16.

NB: Even though intermediate values could be negative, the output must be non-negative since the inputs were non-negative.

fn apply<const N: usize, C>(lhs: [F; N], rhs: [U; N], conv: C) -> [F; N]

where C: Fn([T; N], [U; N], &mut [V]),

Convolve lhs and rhs.

fn conv3(lhs: [T; 3], rhs: [U; 3], output: &mut [V])

fn negacyclic_conv3(lhs: [T; 3], rhs: [U; 3], output: &mut [V])

fn conv4(lhs: [T; 4], rhs: [U; 4], output: &mut [V])

fn negacyclic_conv4(lhs: [T; 4], rhs: [U; 4], output: &mut [V])

fn conv6(lhs: [T; 6], rhs: [U; 6], output: &mut [V])

fn negacyclic_conv6(lhs: [T; 6], rhs: [U; 6], output: &mut [V])

fn conv8(lhs: [T; 8], rhs: [U; 8], output: &mut [V])

fn negacyclic_conv8(lhs: [T; 8], rhs: [U; 8], output: &mut [V])

fn conv12(lhs: [T; 12], rhs: [U; 12], output: &mut [V])

fn negacyclic_conv12(lhs: [T; 12], rhs: [U; 12], output: &mut [V])

fn conv16(lhs: [T; 16], rhs: [U; 16], output: &mut [V])

fn negacyclic_conv16(lhs: [T; 16], rhs: [U; 16], output: &mut [V])

fn conv24(lhs: [T; 24], rhs: [U; 24], output: &mut [V])

fn conv32(lhs: [T; 32], rhs: [U; 32], output: &mut [V])

fn negacyclic_conv32(lhs: [T; 32], rhs: [U; 32], output: &mut [V])

fn conv64(lhs: [T; 64], rhs: [U; 64], output: &mut [V])

impl Debug for Goldilocks

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

Formats the value using the given formatter.

impl Default for Goldilocks

fn default() -> Goldilocks

Returns the “default value” for a type.

impl<'de> Deserialize<'de> for Goldilocks

fn deserialize<__D>(__deserializer: __D) -> Result<Self, __D::Error>

where __D: Deserializer<'de>,

Deserialize this value from the given Serde deserializer.

impl Display for Goldilocks

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

Formats the value using the given formatter.

impl Distribution<Goldilocks> for Standard

fn sample<R: Rng + ?Sized>(&self, rng: &mut R) -> Goldilocks

Generate a random value of T, using rng as the source of randomness.

fn sample_iter<R>(self, rng: R) -> DistIter<Self, R, T>

where R: Rng, Self: Sized,

Create an iterator that generates random values of T, using rng as the source of randomness.

fn map<F, S>(self, func: F) -> DistMap<Self, F, T, S>

where F: Fn(T) -> S, Self: Sized,

Create a distribution of values of ‘S’ by mapping the output of Self through the closure F

impl Div for Goldilocks

type Output = Goldilocks

The resulting type after applying the / operator.

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

Performs the / operation.

impl Field for Goldilocks

const GENERATOR: Self

A generator of this field’s entire multiplicative group.

type Packing = Goldilocks

fn is_zero(&self) -> bool

fn exp_u64_generic<FA: FieldAlgebra<F = Self>>(val: FA, power: u64) -> FA

Exponentiation by a u64 power. This is similar to exp_u64, but more general in that it can be used with FieldAlgebras, not just this concrete field.

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

The multiplicative inverse of this field element, if it exists.

fn halve(&self) -> Self

Computes input/2. Should be overwritten by most field implementations to use bitshifts. Will error if the field characteristic is 2.

fn order() -> BigUint

fn is_one(&self) -> bool

fn div_2exp_u64(&self, exp: u64) -> Self

self / 2^exp

fn inverse(&self) -> Self

fn multiplicative_group_factors() -> Vec<(BigUint, usize)>

A list of (factor, exponent) pairs.

fn bits() -> usize

impl FieldAlgebra for Goldilocks

const ZERO: Self

The additive identity of the algebra.

const ONE: Self

The multiplicative identity of the Algebra

const TWO: Self

The element in the algebra given by ONE + ONE.

const NEG_ONE: Self

The element in the algebra given by -ONE.

type F = Goldilocks

fn from_f(f: Self::F) -> Self

Interpret a field element as a commutative algebra element.

fn from_bool(b: bool) -> Self

Convert from a bool.

fn from_canonical_u8(n: u8) -> Self

Convert from a canonical u8.

fn from_canonical_u16(n: u16) -> Self

Convert from a canonical u16.

fn from_canonical_u32(n: u32) -> Self

Convert from a canonical u32.

fn from_canonical_u64(n: u64) -> Self

Convert from a canonical u64.

fn from_canonical_usize(n: usize) -> Self

Convert from a canonical usize.

fn from_wrapped_u32(n: u32) -> Self

fn from_wrapped_u64(n: u64) -> Self

fn zero_vec(len: usize) -> Vec<Self>

Allocates a vector of zero elements of length len. Many operating systems zero pages before assigning them to a userspace process. In that case, our process should not need to write zeros, which would be redundant. However, the compiler may not always recognize this.

fn double(&self) -> Self

The elementary function double(a) = 2*a.

fn square(&self) -> Self

The elementary function square(a) = a^2.

fn cube(&self) -> Self

The elementary function cube(a) = a^3.

fn exp_u64(&self, power: u64) -> Self

Exponentiation by a u64 power.

fn exp_const_u64<const POWER: u64>(&self) -> Self

Exponentiation by a constant power.

fn exp_power_of_2(&self, power_log: usize) -> Self

Compute self^{2^power_log} by repeated squaring.

fn mul_2exp_u64(&self, exp: u64) -> Self

self * 2^exp

fn powers(&self) -> Powers<Self>

Construct an iterator which returns powers of self: self^0, self^1, self^2, ....

fn shifted_powers(&self, start: Self) -> Powers<Self>

Construct an iterator which returns powers of self shifted by start: start, start*self^1, start*self^2, ....

fn powers_packed<P>(&self) -> Powers<P>

where P: PackedField<Scalar = Self>,

Construct an iterator which returns powers of self packed into PackedField elements.

fn shifted_powers_packed<P>(&self, start: Self) -> Powers<P>

where P: PackedField<Scalar = Self>,

Construct an iterator which returns powers of self shifted by start and packed into PackedField elements.

fn dot_product<const N: usize>(u: &[Self; N], v: &[Self; N]) -> Self

Compute the dot product of two vectors.

impl HasTwoAdicBinomialExtension<2> for Goldilocks

const EXT_TWO_ADICITY: usize = 33usize

fn ext_two_adic_generator(bits: usize) -> [Self; 2]

Assumes the multiplicative group size has at least bits powers of two, otherwise the behavior is undefined.

impl Hash for Goldilocks

fn hash<H: Hasher>(&self, state: &mut H)

Feeds this value into the given Hasher.

fn hash_slice<H>(data: &[Self], state: &mut H)

where H: Hasher, Self: Sized,

Feeds a slice of this type into the given Hasher.

impl Mul for Goldilocks

type Output = Goldilocks

The resulting type after applying the * operator.

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

Performs the * operation.

impl MulAssign for Goldilocks

fn mul_assign(&mut self, rhs: Self)

Performs the *= operation.

impl Neg for Goldilocks

type Output = Goldilocks

The resulting type after applying the - operator.

fn neg(self) -> Self::Output

Performs the unary - operation.

impl Ord for Goldilocks

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

This method returns an Ordering between self and other.

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

where Self: Sized,

Compares and returns the maximum of two values.

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

where Self: Sized,

Compares and returns the minimum of two values.

fn clamp(self, min: Self, max: Self) -> Self

where Self: Sized,

Restrict a value to a certain interval.

impl PartialEq for Goldilocks

fn eq(&self, other: &Self) -> 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 Goldilocks

fn partial_cmp(&self, other: &Self) -> 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 PrimeField for Goldilocks

fn as_canonical_biguint(&self) -> BigUint

impl PrimeField64 for Goldilocks

const ORDER_U64: u64 = 18_446_744_069_414_584_321u64

fn as_canonical_u64(&self) -> u64

Return the representative of value that is less than ORDER_U64.

fn to_unique_u64(&self) -> u64

Convert a field element to a u64 such that any two field elements are converted to the same u64 if and only if they represent the same value.

impl Product for Goldilocks

fn product<I: Iterator<Item = Self>>(iter: I) -> Self

Takes an iterator and generates Self from the elements by multiplying the items.

impl Serialize for Goldilocks

fn serialize<__S>(&self, __serializer: __S) -> Result<__S::Ok, __S::Error>

where __S: Serializer,

Serialize this value into the given Serde serializer.

impl Sub for Goldilocks

type Output = Goldilocks

The resulting type after applying the - operator.

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

Performs the - operation.

impl SubAssign for Goldilocks

fn sub_assign(&mut self, rhs: Self)

Performs the -= operation.

impl Sum for Goldilocks

fn sum<I: Iterator<Item = Self>>(iter: I) -> Self

Takes an iterator and generates Self from the elements by “summing up” the items.

impl TwoAdicField for Goldilocks

const TWO_ADICITY: usize = 32usize

The number of factors of two in this field’s multiplicative group.

fn two_adic_generator(bits: usize) -> Self

Returns a generator of the multiplicative group of order 2^bits. Assumes bits <= TWO_ADICITY, otherwise the result is undefined.

impl Copy for Goldilocks

impl Eq for Goldilocks

impl MdsPermutation<Goldilocks, 12> for MdsMatrixGoldilocks

impl MdsPermutation<Goldilocks, 16> for MdsMatrixGoldilocks

impl MdsPermutation<Goldilocks, 24> for MdsMatrixGoldilocks

impl MdsPermutation<Goldilocks, 32> for MdsMatrixGoldilocks

impl MdsPermutation<Goldilocks, 64> for MdsMatrixGoldilocks

impl MdsPermutation<Goldilocks, 68> for MdsMatrixGoldilocks

impl MdsPermutation<Goldilocks, 8> for MdsMatrixGoldilocks

impl Packable for Goldilocks