Trait ModPowPrecomputed

pub trait ModPowPrecomputed<RHS = Self, M = Self>
where
    Self: Sized,
{
    type Output;
    type Data;

    // Required methods
    fn precompute_mod_pow_data(m: &M) -> Self::Data;
    fn mod_pow_precomputed(
        self,
        exp: RHS,
        m: M,
        data: &Self::Data,
    ) -> Self::Output;
}

Raises a number to a power modulo another number $m$. The base must be already reduced modulo $m$.

If multiple modular exponentiations with the same modulus are necessary, it can be quicker to precompute some piece of data and reuse it in the exponentiation calls. This trait provides a function for precomputing the data and a function for using it during exponentiation.

Required Associated Types

type Output

type Data

Required Methods

fn precompute_mod_pow_data(m: &M) -> Self::Data

Precomputes some data to use for modular exponentiation.

fn mod_pow_precomputed(self, exp: RHS, m: M, data: &Self::Data) -> Self::Output

Dyn Compatibility

This trait is not dyn compatible.

In older versions of Rust, dyn compatibility was called "object safety", so this trait is not object safe.

Implementations on Foreign Types

impl ModPowPrecomputed for u64

fn precompute_mod_pow_data(m: &u64) -> (u64, u64)

Precomputes data for modular exponentiation.

See mod_pow_precomputed and mod_pow_precomputed_assign.

Worst-case complexity

Constant time and additional memory.

fn mod_pow_precomputed(self, exp: u64, m: u64, data: &(u64, u64)) -> u64

Raises a number to a power modulo another number $m$. The base must be already reduced modulo $m$.

Some precomputed data is provided; this speeds up computations involving several modular exponentiations with the same modulus. The precomputed data should be obtained using precompute_mod_pow_data.

Worst-case complexity

$T(n) = O(n)$

$M(n) = O(1)$

where $T$ is time, $M$ is additional memory, and $n$ is exp.significant_bits().

Panics

Panics if self is greater than or equal to m.

Examples

See here.

type Output = u64

type Data = (u64, u64)

impl ModPowPrecomputed<u64> for u8

fn precompute_mod_pow_data(m: &u8) -> (u32, u64)

Precomputes data for modular exponentiation.

See mod_pow_precomputed and mod_pow_precomputed_assign.

Worst-case complexity

Constant time and additional memory.

fn mod_pow_precomputed(self, exp: u64, m: u8, data: &(u32, u64)) -> u8

Raises a number to a power modulo another number $m$. The base must be already reduced modulo $m$.

Some precomputed data is provided; this speeds up computations involving several modular exponentiations with the same modulus. The precomputed data should be obtained using precompute_mod_pow_data.

Worst-case complexity

$T(n) = O(n)$

$M(n) = O(1)$

where $T$ is time, $M$ is additional memory, and $n$ is exp.significant_bits().

Panics

Panics if self is greater than or equal to m.

Examples

See here.

type Output = u8

type Data = (u32, u64)

impl ModPowPrecomputed<u64> for u16

fn precompute_mod_pow_data(m: &u16) -> (u32, u64)

Precomputes data for modular exponentiation.

See mod_pow_precomputed and mod_pow_precomputed_assign.

Worst-case complexity

Constant time and additional memory.

fn mod_pow_precomputed(self, exp: u64, m: u16, data: &(u32, u64)) -> u16

Raises a number to a power modulo another number $m$. The base must be already reduced modulo $m$.

Some precomputed data is provided; this speeds up computations involving several modular exponentiations with the same modulus. The precomputed data should be obtained using precompute_mod_pow_data.

Worst-case complexity

$T(n) = O(n)$

$M(n) = O(1)$

where $T$ is time, $M$ is additional memory, and $n$ is exp.significant_bits().

Panics

Panics if self is greater than or equal to m.

Examples

See here.

type Output = u16

type Data = (u32, u64)

impl ModPowPrecomputed<u64> for u32

fn precompute_mod_pow_data(m: &u32) -> (u32, u64)

Precomputes data for modular exponentiation.

See mod_pow_precomputed and mod_pow_precomputed_assign.

Worst-case complexity

Constant time and additional memory.

fn mod_pow_precomputed(self, exp: u64, m: u32, data: &(u32, u64)) -> u32

Raises a number to a power modulo another number $m$. The base must be already reduced modulo $m$.

Some precomputed data is provided; this speeds up computations involving several modular exponentiations with the same modulus. The precomputed data should be obtained using precompute_mod_pow_data.

Worst-case complexity

$T(n) = O(n)$

$M(n) = O(1)$

where $T$ is time, $M$ is additional memory, and $n$ is exp.significant_bits().

Panics

Panics if self is greater than or equal to m.

Examples

See here.

type Output = u32

type Data = (u32, u64)

impl ModPowPrecomputed<u64> for u128

fn precompute_mod_pow_data(_m: &u128)

Precomputes data for modular exponentiation.

See mod_pow_precomputed and mod_pow_precomputed_assign.

Worst-case complexity

Constant time and additional memory.

fn mod_pow_precomputed(self, exp: u64, m: u128, _data: &()) -> u128

Raises a number to a power modulo another number $m$. The base must be already reduced modulo $m$.

Some precomputed data is provided; this speeds up computations involving several modular exponentiations with the same modulus. The precomputed data should be obtained using precompute_mod_pow_data.

Worst-case complexity

$T(n) = O(n)$

$M(n) = O(1)$

where $T$ is time, $M$ is additional memory, and $n$ is exp.significant_bits().

Panics

Panics if self is greater than or equal to m.

Examples

See here.

type Output = u128

type Data = ()

impl ModPowPrecomputed<u64> for usize

fn precompute_mod_pow_data(m: &usize) -> (usize, u64)

Precomputes data for modular exponentiation.

See mod_pow_precomputed and mod_pow_precomputed_assign.

Worst-case complexity

Constant time and additional memory.

fn mod_pow_precomputed(self, exp: u64, m: usize, data: &(usize, u64)) -> usize

Raises a number to a power modulo another number $m$. The base must be already reduced modulo $m$.

Some precomputed data is provided; this speeds up computations involving several modular exponentiations with the same modulus. The precomputed data should be obtained using precompute_mod_pow_data.

Worst-case complexity

$T(n) = O(n)$

$M(n) = O(1)$

where $T$ is time, $M$ is additional memory, and $n$ is exp.significant_bits().

Panics

Panics if self is greater than or equal to m.

Examples

See here.

type Output = usize

type Data = (usize, u64)

Implementors