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 fn zero() -> FieldElement

Construct zero.

pub fn one() -> FieldElement

Construct one.

pub fn minus_one() -> FieldElement

Construct -1 (mod l).

pub fn is_even(self) -> bool

Evaluate if a FieldElement is even or not.

pub fn generate_random() -> FieldElement

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

Note: It is not possible to invert 0 by obvious reasons. So an assert! check has been implemented to prevent errors.

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 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<'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<'a> Half for &'a FieldElement

type Output = FieldElement

fn half(self) -> FieldElement

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

This function SHOULD ONLY be used with even FieldElements otherways, can produce erroneus results.

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<'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 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 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 Default for FieldElement

fn default() -> FieldElement

Returns the default value for a FieldElement = Zero.

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

fn from(_inp: &'a u8) -> FieldElement

Performs the conversion.

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

fn from(_inp: &'a u16) -> FieldElement

Performs the conversion.

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

fn from(_inp: &'a u32) -> FieldElement

Performs the conversion.

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

fn from(_inp: &'a u64) -> FieldElement

Performs the conversion.

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

fn from(_inp: &'a u128) -> FieldElement

Performs the conversion.

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 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 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 Into<Scalar> for FieldElement

fn into(self) -> Ristretto255Scalar

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

impl Copy for FieldElement

impl Eq for FieldElement

impl Debug for FieldElement

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

Formats the value using the given formatter.

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<'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).

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, '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 equivanelnt 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 equivanelnt op is: x * (y^-1 (mod l)), which is equivalent to the naive division but for Finite Fields.

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 correspond's to the two's complement of the input FieldElement.

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.