[−][src]Trait zerocaf::traits::ops::ModSqrt

pub trait ModSqrt {
    type Output;
#[must_use]
    fn mod_sqrt(self, choice: Choice) -> Self::Output;
}

Associated Types

type Output

Loading content...

Required methods

#[must_use] fn mod_sqrt(self, choice: Choice) -> Self::Output

Performs the modular Square Root operation over a finite field ie. sqrt(x) (mod l).

With the given Choice, the impl is able to provide the result that corresponds to the positive or negative sign choosen.

Returns

Some(symb_choosen_result) if the input is a QR for the prime modulo. Otherways it returns None

Loading content...

Implementors

impl<'a> ModSqrt for &'a FieldElement[src]

type Output = Option<FieldElement>

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

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

Loading content...