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

[+] Show declaration

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

[−] Expand description

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[+]

[+] Show hidden undocumented items

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[+]

[+] Show hidden undocumented items

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[+]

[+] Show hidden undocumented items

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[+]

[+] Show hidden undocumented items

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[+]

[+] Show hidden undocumented items

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[+]

[+] Show hidden undocumented items

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[+]

[+] Show hidden undocumented items

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

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

[+] Expand attributes

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

This method tests for !=.

impl PartialOrd<FieldElement> for FieldElement[+]

[+] Show hidden undocumented items

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

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

[+] Expand attributes

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

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

[+] Expand attributes

#[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.

[+] Expand attributes

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

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

[+] Expand attributes

#[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).