Struct zerocaf::backend::u64::field::FieldElement

pub struct FieldElement(pub [u64; 5]);

A FieldElement represents an element of the field which has order of 2^252 + 27742317777372353535851937790883648493

In the 64-bit backend implementation, the FieldElement is represented in radix 2^52

Methods

impl FieldElement

pub const fn zero() -> FieldElement

Construct zero.

pub const fn one() -> FieldElement

Construct one.

pub const fn minus_one() -> FieldElement

Construct -1 (mod l).

pub fn is_even(self) -> bool

Evaluate if a FieldElement is even or not.

pub fn is_positive(&self) -> Choice

Checks if a ´FieldElement` is considered negative following the Decaf paper criteria.

The criteria says: Non-negative field elements. Let p > 2 be prime. Define a residue x ∈ F =Z/pZ to be “non-negative” if the least absolute residue for x is in [0,(p−1)/2], and “negative” otherwise.

Returns:

• Choice(1) if pos.
• Choice(0) if neg.

pub fn from_bytes(bytes: &[u8; 32]) -> FieldElement

Load a FieldElement from the low 253b bits of a 256-bit input. So Little Endian representation in bytes of a FieldElement.

pub fn to_bytes(self) -> [u8; 32]

Serialize this FieldElement to a 32-byte array. The encoding is canonical.

pub fn two_pow_k(exp: u64) -> FieldElement

Given a k: u64, compute 2^k giving the resulting result as a FieldElement.

See that the input must be between the range => 0..253.

NOTE: This function implements an assert! statement that checks the correctness of the exponent provided as param.

pub fn half_without_mod(self) -> FieldElement

Returns the half of an EVEN FieldElement.

This function performs almost 4x faster than the Half implementation but SHOULD be used carefully.

Panics

When the FieldElement provided is not even.

pub fn legendre_symbol(&self) -> Choice

Given a FieldElement, this function evaluates if it is a quadratic residue (mod l).

See: https://en.wikipedia.org/wiki/Legendre_symbol.

Returns:

-1 -> Non-quadratic residue (mod l) == Choice(0).

1 -> Quadratic residue (mod l) == Choice(1).

0 -> Input (mod l) == 0. Not implemented since you can't pass an input which is multiple of FIELD_L.

pub fn inverse(&self) -> FieldElement

Compute a^-1 (mod l) using the the Savas & Koç modular inverse algorithm. It's an optimization of the Kalinski modular inversion algorithm that extends the Binary GCD algorithm to perform the modular inverse operation.

The PhaseII it's substituded by 1 or 2 Montgomery Multiplications, what makes the second part compute in almost ConstTime.

Panics

It is not possible to invert 0 by obvious reasons. So an the function panics when trying to invert zero.

Special issue on Montgomery arithmetic. Montgomery inversion - Erkay Sava ̧s & Çetin Kaya Koç J Cryptogr Eng (2018) 8:201–210 https://doi.org/10.1007/s13389-017-0161-x.

Trait Implementations

impl<'a, 'b> Add<&'b FieldElement> for &'a FieldElement

type Output = FieldElement

The resulting type after applying the + operator.

fn add(self, b: &'b FieldElement) -> FieldElement

Compute a + b (mod l).

impl Add<FieldElement> for FieldElement

type Output = FieldElement

The resulting type after applying the + operator.

fn add(self, b: FieldElement) -> FieldElement

Compute a + b (mod l).

impl Clone for FieldElement

fn clone(&self) -> FieldElement

Returns a copy of the value.

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

Performs copy-assignment from source.

impl Copy for FieldElement

impl Debug for FieldElement

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

Formats the value using the given formatter.

impl Default for FieldElement

fn default() -> FieldElement

Returns the default value for a FieldElement = Zero.

impl Display for FieldElement

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

Formats the value using the given formatter.

impl<'a, 'b> Div<&'a FieldElement> for &'b FieldElement

type Output = FieldElement

The resulting type after applying the / operator.

fn div(self, _rhs: &'a FieldElement) -> FieldElement

Performs the op: x / y (mod l).

Since on modular fields we don't divide, the equivalent op is: x * (y^-1 (mod l)), which is equivalent to the naive division but for Finite Fields.

impl Div<FieldElement> for FieldElement

type Output = FieldElement

The resulting type after applying the / operator.

fn div(self, _rhs: FieldElement) -> FieldElement

Performs the op: x / y (mod l).

Since on modular fields we don't divide, the equivalent op is: x * (y^-1 (mod l)), which is equivalent to the naive division but for Finite Fields.

impl Eq for FieldElement

impl<'a> From<&'a Scalar> for FieldElement

fn from(origin: &'a Ristretto255Scalar) -> FieldElement

Given a Ristretto255Scalar on canonical bytes representation get it's FieldElement equivalent value as 5 limbs and radix-52.

impl From<u128> for FieldElement

fn from(_inp: u128) -> FieldElement

Performs the conversion.

impl From<u16> for FieldElement

fn from(_inp: u16) -> FieldElement

Performs the conversion.

impl From<u32> for FieldElement

fn from(_inp: u32) -> FieldElement

Performs the conversion.

impl From<u64> for FieldElement

fn from(_inp: u64) -> FieldElement

Performs the conversion.

impl From<u8> for FieldElement

fn from(_inp: u8) -> FieldElement

Performs the conversion.

impl<'a> Half for &'a FieldElement

type Output = FieldElement

fn half(self) -> FieldElement

Give the half of the FieldElement value (mod l).

impl Identity for FieldElement

fn identity() -> FieldElement

Returns the Identity element over the finite field modulo 2^252 + 27742317777372353535851937790883648493.

It is defined as 1 on FieldElement format, and is therefore written as: [1, 0, 0, 0, 0].

impl Index<usize> for FieldElement

type Output = u64

The returned type after indexing.

fn index(&self, _index: usize) -> &u64

Performs the indexing (container[index]) operation.

impl IndexMut<usize> for FieldElement

fn index_mut(&mut self, _index: usize) -> &mut u64

Performs the mutable indexing (container[index]) operation.

impl Into<Scalar> for FieldElement

fn into(self) -> Ristretto255Scalar

Given a FieldElement reference get it's Ristretto255Scalar Equivalent on it's canonical bytes representation.

impl<'_> InvSqrt for &'_ FieldElement

type Output = (Choice, FieldElement)

fn inv_sqrt(self) -> (Choice, FieldElement)

This is a convenience wrapper function over the SqrtRatioI trait implementation when self = 1: Computes sqrt(1/self).

This function always returns the non-negative result of the sqrt.

Returns:

• (Choice(1), +sqrt(1/self)) if self is a nonzero square;
• (Choice(0), zero) if self is zero;
• (Choice(0), +sqrt(i/self)) if self is a nonzero nonsquare;

impl<'a> ModSqrt for &'a FieldElement

type Output = Option<FieldElement>

fn mod_sqrt(self, sign: Choice) -> Option<FieldElement>

Performs the op: sqrt(a) (mod l).

Tonelli-Shanks prime modular square root algorithm implementation for FieldElement.

Conditionally selects and returns the positive or the negative result of the mod_sqrt by analyzing the Choice sent as input:

For Choice(0) -> Negative result. For Choice(1) -> Positive result.

Daniel Shanks. Five Number Theoretic Algorithms. Proceedings of the Second Manitoba Conference on Numerical Mathematics. Pp. 51–70. 1973.

This algorithm was translated from the python impl found in: https://codereview.stackexchange.com/questions/43210/tonelli-shanks-algorithm-implementation-of-prime-modular-square-root

impl<'a, 'b> Mul<&'b FieldElement> for &'a FieldElement

type Output = FieldElement

The resulting type after applying the * operator.

fn mul(self, _rhs: &'b FieldElement) -> FieldElement

This Mul implementation returns a double precision result.

The result of the standard mul is stored on a [u128; 9].

Then, we apply the Montgomery Reduction function to perform the modulo and the reduction to the FieldElement format: [u64; 5].

impl Mul<FieldElement> for FieldElement

type Output = FieldElement

The resulting type after applying the * operator.

fn mul(self, _rhs: FieldElement) -> FieldElement

This Mul implementation returns a double precision result.

The result of the standard mul is stored on a [u128; 9].

Then, we apply the Montgomery Reduction function to perform the modulo and the reduction to the FieldElement format: [u64; 5].

impl<'a> Neg for &'a FieldElement

type Output = FieldElement

The resulting type after applying the - operator.

fn neg(self) -> FieldElement

Computes -self (mod l). Compute the negated value that corresponds to the complement of the two, of the input FieldElement.

impl Neg for FieldElement

type Output = FieldElement

The resulting type after applying the - operator.

fn neg(self) -> FieldElement

Computes -self (mod l).

Compute the negated value that corresponds to the two's complement of the input FieldElement.

impl Ord for FieldElement

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

This method returns an Ordering between self and other.

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

Compares and returns the maximum of two values.

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

Compares and returns the minimum of two values.

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

🔬 This is a nightly-only experimental API. (clamp)

Restrict a value to a certain interval.

impl PartialEq<FieldElement> for FieldElement

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

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

#[must_use] fn ne(&self, other: &Rhs) -> bool

This method tests for !=.

impl PartialOrd<FieldElement> for FieldElement

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

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

#[must_use] fn lt(&self, other: &Rhs) -> bool

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

#[must_use] fn le(&self, other: &Rhs) -> bool

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

#[must_use] fn gt(&self, other: &Rhs) -> bool

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

#[must_use] 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<'a, 'b> Pow<&'b FieldElement> for &'a FieldElement

type Output = FieldElement

fn pow(self, exp: &'b FieldElement) -> FieldElement

Performs the op: a^b (mod l).

Exponentiation by squaring classical algorithm implementation for FieldElement.

Schneier, Bruce (1996). Applied Cryptography: Protocols, Algorithms, and Source Code in C, Second Edition (2nd ed.).

impl<'_> SqrtRatioI<&'_ FieldElement> for FieldElement

type Output = (Choice, FieldElement)

fn sqrt_ratio_i(&self, v: &FieldElement) -> (Choice, FieldElement)

The first part of the return value signals whether u/v was square, and the second part contains a square root. Specifically, it returns:

• (true, +sqrt(u/v)) if v is nonzero and u/v is square;
• (true, zero) if u is zero;
• (false, zero) if v is zero and u is nonzero;
• (false, +sqrt(i*u/v)) if u/v is nonsquare (so iu/v is square).

impl<'a> Square for &'a FieldElement

type Output = FieldElement

fn square(self) -> FieldElement

Compute a^2 (mod l).

This Square implementation returns a double precision result. The result of the standard square is stored on a [u128; 9].

Then, we apply the Montgomery Reduction function to perform the modulo and the reduction to the FieldElement format: [u64; 5].

impl StructuralEq for FieldElement

impl<'a, 'b> Sub<&'b FieldElement> for &'a FieldElement

type Output = FieldElement

The resulting type after applying the - operator.

fn sub(self, b: &'b FieldElement) -> FieldElement

Compute a - b (mod l)

impl Sub<FieldElement> for FieldElement

type Output = FieldElement

The resulting type after applying the - operator.

fn sub(self, b: FieldElement) -> FieldElement

Compute a + b (mod l).