Trait malachite_base::num::arithmetic::traits::LegendreSymbol

source · [−]
pub trait LegendreSymbol<RHS = Self> {
    fn legendre_symbol(self, other: RHS) -> i8;
}
Expand description

Calculates the Legendre symbol of two numbers. Typically the implementations will be identical to those of JacobiSymbol.

Required Methods

Implementations on Foreign Types

Computes the Legendre symbol of two numbers.

This implementation is identical to that of JacobiSymbol, since there is no computational benefit to requiring that the denominator be prime.

$$ f(x, y) = \left ( \frac{x}{y} \right ). $$

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(), other.significant_bits()).

Panics

Panics if n is even.

Examples

See here.

Computes the Legendre symbol of two numbers.

This implementation is identical to that of JacobiSymbol, since there is no computational benefit to requiring that the denominator be prime.

$$ f(x, y) = \left ( \frac{x}{y} \right ). $$

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(), other.significant_bits()).

Panics

Panics if n is even or negative.

Examples

See here.

Computes the Legendre symbol of two numbers.

This implementation is identical to that of JacobiSymbol, since there is no computational benefit to requiring that the denominator be prime.

$$ f(x, y) = \left ( \frac{x}{y} \right ). $$

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(), other.significant_bits()).

Panics

Panics if n is even.

Examples

See here.

Computes the Legendre symbol of two numbers.

This implementation is identical to that of JacobiSymbol, since there is no computational benefit to requiring that the denominator be prime.

$$ f(x, y) = \left ( \frac{x}{y} \right ). $$

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(), other.significant_bits()).

Panics

Panics if n is even or negative.

Examples

See here.

Computes the Legendre symbol of two numbers.

This implementation is identical to that of JacobiSymbol, since there is no computational benefit to requiring that the denominator be prime.

$$ f(x, y) = \left ( \frac{x}{y} \right ). $$

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(), other.significant_bits()).

Panics

Panics if n is even.

Examples

See here.

Computes the Legendre symbol of two numbers.

This implementation is identical to that of JacobiSymbol, since there is no computational benefit to requiring that the denominator be prime.

$$ f(x, y) = \left ( \frac{x}{y} \right ). $$

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(), other.significant_bits()).

Panics

Panics if n is even or negative.

Examples

See here.

Computes the Legendre symbol of two numbers.

This implementation is identical to that of JacobiSymbol, since there is no computational benefit to requiring that the denominator be prime.

$$ f(x, y) = \left ( \frac{x}{y} \right ). $$

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(), other.significant_bits()).

Panics

Panics if n is even.

Examples

See here.

Computes the Legendre symbol of two numbers.

This implementation is identical to that of JacobiSymbol, since there is no computational benefit to requiring that the denominator be prime.

$$ f(x, y) = \left ( \frac{x}{y} \right ). $$

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(), other.significant_bits()).

Panics

Panics if n is even or negative.

Examples

See here.

Computes the Legendre symbol of two numbers.

This implementation is identical to that of JacobiSymbol, since there is no computational benefit to requiring that the denominator be prime.

$$ f(x, y) = \left ( \frac{x}{y} \right ). $$

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(), other.significant_bits()).

Panics

Panics if n is even.

Examples

See here.

Computes the Legendre symbol of two numbers.

This implementation is identical to that of JacobiSymbol, since there is no computational benefit to requiring that the denominator be prime.

$$ f(x, y) = \left ( \frac{x}{y} \right ). $$

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(), other.significant_bits()).

Panics

Panics if n is even or negative.

Examples

See here.

Computes the Legendre symbol of two numbers.

This implementation is identical to that of JacobiSymbol, since there is no computational benefit to requiring that the denominator be prime.

$$ f(x, y) = \left ( \frac{x}{y} \right ). $$

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(), other.significant_bits()).

Panics

Panics if n is even.

Examples

See here.

Computes the Legendre symbol of two numbers.

This implementation is identical to that of JacobiSymbol, since there is no computational benefit to requiring that the denominator be prime.

$$ f(x, y) = \left ( \frac{x}{y} \right ). $$

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(), other.significant_bits()).

Panics

Panics if n is even or negative.

Examples

See here.

Implementors