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

pub trait LegendreSymbol<RHS = Self> {
    // Required method
    fn legendre_symbol(self, other: RHS) -> i8;
}

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

Required Methods

fn legendre_symbol(self, other: RHS) -> i8

Implementations on Foreign Types

impl LegendreSymbol for i8

fn legendre_symbol(self, n: i8) -> i8

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.

impl LegendreSymbol for i16

fn legendre_symbol(self, n: i16) -> i8

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.

impl LegendreSymbol for i32

fn legendre_symbol(self, n: i32) -> i8

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.

impl LegendreSymbol for i64

fn legendre_symbol(self, n: i64) -> i8

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.

impl LegendreSymbol for i128

fn legendre_symbol(self, n: i128) -> i8

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.

impl LegendreSymbol for isize

fn legendre_symbol(self, n: isize) -> i8

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.

impl LegendreSymbol for u8

fn legendre_symbol(self, n: u8) -> i8

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.

impl LegendreSymbol for u16

fn legendre_symbol(self, n: u16) -> i8

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.

impl LegendreSymbol for u32

fn legendre_symbol(self, n: u32) -> i8

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.

impl LegendreSymbol for u64

fn legendre_symbol(self, n: u64) -> i8

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.

impl LegendreSymbol for u128

fn legendre_symbol(self, n: u128) -> i8

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.

impl LegendreSymbol for usize

fn legendre_symbol(self, n: usize) -> i8

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.

Implementors