Trait ModSqrt 

pub trait ModSqrt<M = Self> {
    type Output;

    // Required method
    fn mod_sqrt(self, m: M) -> Option<Self::Output>;
}

Computes a square root of a number modulo another number $m$, returning None if no root is found. The input must be already reduced modulo $m$.

The modulus should be an odd prime: for such moduli a root is found whenever one exists. The behavior for other moduli is deterministic and never hangs, but a root may be missed, and a returned value may fail to be a root.

Required Associated Types

type Output

Required Methods

fn mod_sqrt(self, m: M) -> Option<Self::Output>

Dyn Compatibility

This trait is dyn compatible.

In older versions of Rust, dyn compatibility was called "object safety".

Implementations on Foreign Types

impl ModSqrt for u8

fn mod_sqrt(self, m: u8) -> Option<u8>

Computes a square root of a number modulo another number $m$: a $y$ with $y^2 \equiv x \pmod m$. The input must be already reduced modulo $m$.

If $m$ is an odd prime, a root is returned whenever one exists, and None is returned exactly when $x$ is a quadratic nonresidue. For other moduli the function still terminates and is deterministic, but it may return None even though a root exists, and it may return a value that is not a root, so if $m$ is not known to be prime, a returned root should be verified by squaring. The behavior for such moduli matches FLINT’s, with two exceptions, both involving only composite moduli: for even moduli between 50 and 600 FLINT consults a Jacobi-symbol routine whose behavior for even moduli is undefined, and for the two largest odd moduli of a width FLINT’s exponent computations wrap, while this function computes them exactly, as FLINT’s own multiprecision path does.

$f(x, m) = y$, where $x, y < m$ and $y^2 \equiv x \mod m$, if such a $y$ is found.

Worst-case complexity

$T(n) = O(n^2)$

$M(n) = O(1)$

where $T$ is time, $M$ is additional memory, and $n$ is m.significant_bits(). The bound assumes that the quadratic-nonresidue search does not dominate; under the extended Riemann hypothesis the search inspects $O((\log m)^2)$ candidates.

Panics

Panics if self is greater than or equal to m.

Examples

See here.

This is equivalent to n_sqrtmod from ulong_extras/sqrtmod.c, FLINT 3.6.0, returning an Option where FLINT returns 0 for both a failure and a root of 0.

type Output = u8

impl ModSqrt for u16

fn mod_sqrt(self, m: u16) -> Option<u16>

Computes a square root of a number modulo another number $m$: a $y$ with $y^2 \equiv x \pmod m$. The input must be already reduced modulo $m$.

If $m$ is an odd prime, a root is returned whenever one exists, and None is returned exactly when $x$ is a quadratic nonresidue. For other moduli the function still terminates and is deterministic, but it may return None even though a root exists, and it may return a value that is not a root, so if $m$ is not known to be prime, a returned root should be verified by squaring. The behavior for such moduli matches FLINT’s, with two exceptions, both involving only composite moduli: for even moduli between 50 and 600 FLINT consults a Jacobi-symbol routine whose behavior for even moduli is undefined, and for the two largest odd moduli of a width FLINT’s exponent computations wrap, while this function computes them exactly, as FLINT’s own multiprecision path does.

$f(x, m) = y$, where $x, y < m$ and $y^2 \equiv x \mod m$, if such a $y$ is found.

Worst-case complexity

$T(n) = O(n^2)$

$M(n) = O(1)$

where $T$ is time, $M$ is additional memory, and $n$ is m.significant_bits(). The bound assumes that the quadratic-nonresidue search does not dominate; under the extended Riemann hypothesis the search inspects $O((\log m)^2)$ candidates.

Panics

Panics if self is greater than or equal to m.

Examples

See here.

This is equivalent to n_sqrtmod from ulong_extras/sqrtmod.c, FLINT 3.6.0, returning an Option where FLINT returns 0 for both a failure and a root of 0.

type Output = u16

impl ModSqrt for u32

fn mod_sqrt(self, m: u32) -> Option<u32>

Computes a square root of a number modulo another number $m$: a $y$ with $y^2 \equiv x \pmod m$. The input must be already reduced modulo $m$.

If $m$ is an odd prime, a root is returned whenever one exists, and None is returned exactly when $x$ is a quadratic nonresidue. For other moduli the function still terminates and is deterministic, but it may return None even though a root exists, and it may return a value that is not a root, so if $m$ is not known to be prime, a returned root should be verified by squaring. The behavior for such moduli matches FLINT’s, with two exceptions, both involving only composite moduli: for even moduli between 50 and 600 FLINT consults a Jacobi-symbol routine whose behavior for even moduli is undefined, and for the two largest odd moduli of a width FLINT’s exponent computations wrap, while this function computes them exactly, as FLINT’s own multiprecision path does.

$f(x, m) = y$, where $x, y < m$ and $y^2 \equiv x \mod m$, if such a $y$ is found.

Worst-case complexity

$T(n) = O(n^2)$

$M(n) = O(1)$

where $T$ is time, $M$ is additional memory, and $n$ is m.significant_bits(). The bound assumes that the quadratic-nonresidue search does not dominate; under the extended Riemann hypothesis the search inspects $O((\log m)^2)$ candidates.

Panics

Panics if self is greater than or equal to m.

Examples

See here.

This is equivalent to n_sqrtmod from ulong_extras/sqrtmod.c, FLINT 3.6.0, returning an Option where FLINT returns 0 for both a failure and a root of 0.

type Output = u32

impl ModSqrt for u64

fn mod_sqrt(self, m: u64) -> Option<u64>

Computes a square root of a number modulo another number $m$: a $y$ with $y^2 \equiv x \pmod m$. The input must be already reduced modulo $m$.

If $m$ is an odd prime, a root is returned whenever one exists, and None is returned exactly when $x$ is a quadratic nonresidue. For other moduli the function still terminates and is deterministic, but it may return None even though a root exists, and it may return a value that is not a root, so if $m$ is not known to be prime, a returned root should be verified by squaring. The behavior for such moduli matches FLINT’s, with two exceptions, both involving only composite moduli: for even moduli between 50 and 600 FLINT consults a Jacobi-symbol routine whose behavior for even moduli is undefined, and for the two largest odd moduli of a width FLINT’s exponent computations wrap, while this function computes them exactly, as FLINT’s own multiprecision path does.

$f(x, m) = y$, where $x, y < m$ and $y^2 \equiv x \mod m$, if such a $y$ is found.

Worst-case complexity

$T(n) = O(n^2)$

$M(n) = O(1)$

where $T$ is time, $M$ is additional memory, and $n$ is m.significant_bits(). The bound assumes that the quadratic-nonresidue search does not dominate; under the extended Riemann hypothesis the search inspects $O((\log m)^2)$ candidates.

Panics

Panics if self is greater than or equal to m.

Examples

See here.

This is equivalent to n_sqrtmod from ulong_extras/sqrtmod.c, FLINT 3.6.0, returning an Option where FLINT returns 0 for both a failure and a root of 0.

type Output = u64

impl ModSqrt for u128

fn mod_sqrt(self, m: u128) -> Option<u128>

Computes a square root of a number modulo another number $m$: a $y$ with $y^2 \equiv x \pmod m$. The input must be already reduced modulo $m$.

If $m$ is an odd prime, a root is returned whenever one exists, and None is returned exactly when $x$ is a quadratic nonresidue. For other moduli the function still terminates and is deterministic, but it may return None even though a root exists, and it may return a value that is not a root, so if $m$ is not known to be prime, a returned root should be verified by squaring. The behavior for such moduli matches FLINT’s, with two exceptions, both involving only composite moduli: for even moduli between 50 and 600 FLINT consults a Jacobi-symbol routine whose behavior for even moduli is undefined, and for the two largest odd moduli of a width FLINT’s exponent computations wrap, while this function computes them exactly, as FLINT’s own multiprecision path does.

$f(x, m) = y$, where $x, y < m$ and $y^2 \equiv x \mod m$, if such a $y$ is found.

Worst-case complexity

$T(n) = O(n^2)$

$M(n) = O(1)$

where $T$ is time, $M$ is additional memory, and $n$ is m.significant_bits(). The bound assumes that the quadratic-nonresidue search does not dominate; under the extended Riemann hypothesis the search inspects $O((\log m)^2)$ candidates.

Panics

Panics if self is greater than or equal to m.

Examples

See here.

This is equivalent to n_sqrtmod from ulong_extras/sqrtmod.c, FLINT 3.6.0, returning an Option where FLINT returns 0 for both a failure and a root of 0.

type Output = u128

impl ModSqrt for usize

fn mod_sqrt(self, m: Self) -> Option<Self>

Computes a square root of a number modulo another number $m$: a $y$ with $y^2 \equiv x \pmod m$. The input must be already reduced modulo $m$.

If $m$ is an odd prime, a root is returned whenever one exists, and None is returned exactly when $x$ is a quadratic nonresidue. For other moduli the function still terminates and is deterministic, but it may return None even though a root exists, and it may return a value that is not a root, so if $m$ is not known to be prime, a returned root should be verified by squaring. The behavior for such moduli matches FLINT’s, with two exceptions, both involving only composite moduli: for even moduli between 50 and 600 FLINT consults a Jacobi-symbol routine whose behavior for even moduli is undefined, and for the two largest odd moduli of a width FLINT’s exponent computations wrap, while this function computes them exactly, as FLINT’s own multiprecision path does.

$f(x, m) = y$, where $x, y < m$ and $y^2 \equiv x \mod m$, if such a $y$ is found.

Worst-case complexity

$T(n) = O(n^2)$

$M(n) = O(1)$

where $T$ is time, $M$ is additional memory, and $n$ is m.significant_bits(). The bound assumes that the quadratic-nonresidue search does not dominate; under the extended Riemann hypothesis the search inspects $O((\log m)^2)$ candidates.

Panics

Panics if self is greater than or equal to m.

Examples

See here.

This is equivalent to n_sqrtmod from ulong_extras/sqrtmod.c, FLINT 3.6.0, returning an Option where FLINT returns 0 for both a failure and a root of 0.

type Output = usize

Implementors