Trait malachite_base::num::arithmetic::traits::ModInverse

source · 
pub trait ModInverse<M = Self> {
    type Output;

    fn mod_inverse(self, m: M) -> Option<Self::Output>;
}
Expand description

Finds the multiplicative inverse of a number modulo another number $m$. Assumes the input is already reduced modulo $m$.

Required Associated Types§

Required Methods§

Implementations on Foreign Types§

Computes the multiplicative inverse of a number modulo another number $m$. Assumes the first number is already reduced modulo $m$.

Returns None if $x$ and $m$ are not coprime.

$f(x, m) = y$, where $x, y < m$, $\gcd(x, y) = 1$, and $xy \equiv 1 \mod m$.

Worst-case complexity

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

$M(n) = O(n)$

where $T$ is time, $M$ is additional memory, and $n$ is max(self.significant_bits(), m.significant_bits()).

Examples

See here.

Computes the multiplicative inverse of a number modulo another number $m$. Assumes the first number is already reduced modulo $m$.

Returns None if $x$ and $m$ are not coprime.

$f(x, m) = y$, where $x, y < m$, $\gcd(x, y) = 1$, and $xy \equiv 1 \mod m$.

Worst-case complexity

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

$M(n) = O(n)$

where $T$ is time, $M$ is additional memory, and $n$ is max(self.significant_bits(), m.significant_bits()).

Examples

See here.

Computes the multiplicative inverse of a number modulo another number $m$. Assumes the first number is already reduced modulo $m$.

Returns None if $x$ and $m$ are not coprime.

$f(x, m) = y$, where $x, y < m$, $\gcd(x, y) = 1$, and $xy \equiv 1 \mod m$.

Worst-case complexity

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

$M(n) = O(n)$

where $T$ is time, $M$ is additional memory, and $n$ is max(self.significant_bits(), m.significant_bits()).

Examples

See here.

Computes the multiplicative inverse of a number modulo another number $m$. Assumes the first number is already reduced modulo $m$.

Returns None if $x$ and $m$ are not coprime.

$f(x, m) = y$, where $x, y < m$, $\gcd(x, y) = 1$, and $xy \equiv 1 \mod m$.

Worst-case complexity

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

$M(n) = O(n)$

where $T$ is time, $M$ is additional memory, and $n$ is max(self.significant_bits(), m.significant_bits()).

Examples

See here.

Computes the multiplicative inverse of a number modulo another number $m$. Assumes the first number is already reduced modulo $m$.

Returns None if $x$ and $m$ are not coprime.

$f(x, m) = y$, where $x, y < m$, $\gcd(x, y) = 1$, and $xy \equiv 1 \mod m$.

Worst-case complexity

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

$M(n) = O(n)$

where $T$ is time, $M$ is additional memory, and $n$ is max(self.significant_bits(), m.significant_bits()).

Examples

See here.

Computes the multiplicative inverse of a number modulo another number $m$. Assumes the first number is already reduced modulo $m$.

Returns None if $x$ and $m$ are not coprime.

$f(x, m) = y$, where $x, y < m$, $\gcd(x, y) = 1$, and $xy \equiv 1 \mod m$.

Worst-case complexity

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

$M(n) = O(n)$

where $T$ is time, $M$ is additional memory, and $n$ is max(self.significant_bits(), m.significant_bits()).

Examples

See here.

Implementors§