Trait ModMulPrecomputed

pub trait ModMulPrecomputed<RHS = Self, M = Self> {
    type Output;
    type Data;

    // Required methods
    fn precompute_mod_mul_data(m: &M) -> Self::Data;
    fn mod_mul_precomputed(
        self,
        other: RHS,
        m: M,
        data: &Self::Data,
    ) -> Self::Output;
}

Multiplies two numbers modulo a third number $m$. The inputs must be already reduced modulo $m$.

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

Required Associated Types

type Output

type Data

Required Methods

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

Precomputes some data to use for modular multiplication.

fn mod_mul_precomputed( self, other: 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 ModMulPrecomputed for u8

fn precompute_mod_mul_data(m: &u8) -> u32

Precomputes data for modular multiplication. See mod_mul_precomputed and mod_mul_precomputed_assign.

Worst-case complexity

Constant time and additional memory.

This is equivalent to n_preinvert_limb from ulong_extras.h, FLINT 2.7.1.

fn mod_mul_precomputed(self, other: u8, m: u8, data: &u32) -> u8

Multiplies two numbers modulo a third number $m$. The inputs must be already reduced modulo $m$.

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

Worst-case complexity

Constant time and additional memory.

Panics

Panics if self or other are greater than or equal to m.

Examples

See here.

This is equivalent to n_mulmod2_preinv from ulong_extras.h, FLINT 2.7.1.

type Output = u8

type Data = u32

impl ModMulPrecomputed for u16

fn precompute_mod_mul_data(m: &u16) -> u32

Precomputes data for modular multiplication. See mod_mul_precomputed and mod_mul_precomputed_assign.

Worst-case complexity

Constant time and additional memory.

This is equivalent to n_preinvert_limb from ulong_extras.h, FLINT 2.7.1.

fn mod_mul_precomputed(self, other: u16, m: u16, data: &u32) -> u16

Multiplies two numbers modulo a third number $m$. The inputs must be already reduced modulo $m$.

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

Worst-case complexity

Constant time and additional memory.

Panics

Panics if self or other are greater than or equal to m.

Examples

See here.

This is equivalent to n_mulmod2_preinv from ulong_extras.h, FLINT 2.7.1.

type Output = u16

type Data = u32

impl ModMulPrecomputed for u32

fn precompute_mod_mul_data(m: &u32) -> u32

Precomputes data for modular multiplication. See mod_mul_precomputed and mod_mul_precomputed_assign.

Worst-case complexity

Constant time and additional memory.

This is equivalent to n_preinvert_limb from ulong_extras.h, FLINT 2.7.1.

fn mod_mul_precomputed(self, other: u32, m: u32, data: &u32) -> u32

Multiplies two numbers modulo a third number $m$. The inputs must be already reduced modulo $m$.

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

Worst-case complexity

Constant time and additional memory.

Panics

Panics if self or other are greater than or equal to m.

Examples

See here.

This is equivalent to n_mulmod2_preinv from ulong_extras.h, FLINT 2.7.1.

type Output = u32

type Data = u32

impl ModMulPrecomputed for u64

fn precompute_mod_mul_data(m: &u64) -> u64

Precomputes data for modular multiplication. See mod_mul_precomputed and mod_mul_precomputed_assign.

Worst-case complexity

Constant time and additional memory.

This is equivalent to n_preinvert_limb from ulong_extras.h, FLINT 2.7.1.

fn mod_mul_precomputed(self, other: u64, m: u64, data: &u64) -> u64

Multiplies two numbers modulo a third number $m$. The inputs must be already reduced modulo $m$.

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

Worst-case complexity

Constant time and additional memory.

Panics

Panics if self or other are greater than or equal to m.

Examples

See here.

This is equivalent to n_mulmod2_preinv from ulong_extras.h, FLINT 2.7.1.

type Output = u64

type Data = u64

impl ModMulPrecomputed for u128

fn precompute_mod_mul_data(_m: &u128)

Precomputes data for modular multiplication. See mod_mul_precomputed and mod_mul_precomputed_assign.

Worst-case complexity

Constant time and additional memory.

fn mod_mul_precomputed(self, other: u128, m: u128, _data: &()) -> u128

Multiplies two numbers modulo a third number $m$. The inputs must be already reduced modulo $m$.

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

Worst-case complexity

Constant time and additional memory.

Panics

Panics if self or other are greater than or equal to m.

Examples

See here.

This is equivalent to n_mulmod2_preinv from ulong_extras.h, FLINT 2.7.1.

type Output = u128

type Data = ()

impl ModMulPrecomputed for usize

fn precompute_mod_mul_data(m: &usize) -> usize

Precomputes data for modular multiplication. See mod_mul_precomputed and mod_mul_precomputed_assign.

Worst-case complexity

Constant time and additional memory.

This is equivalent to n_preinvert_limb from ulong_extras.h, FLINT 2.7.1.

fn mod_mul_precomputed(self, other: usize, m: usize, data: &usize) -> usize

Multiplies two numbers modulo a third number $m$. The inputs must be already reduced modulo $m$.

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

Worst-case complexity

Constant time and additional memory.

Panics

Panics if self or other are greater than or equal to m.

Examples

See here.

This is equivalent to n_mulmod2_preinv from ulong_extras.h, FLINT 2.7.1.

type Output = usize

type Data = usize

Implementors