Trait malachite_base::num::arithmetic::traits::ModMulPrecomputed
source · [−]pub trait ModMulPrecomputed<RHS = Self, M = Self> {
type Output;
type Data;
fn precompute_mod_mul_data(m: &M) -> Self::Data;
fn mod_mul_precomputed(
self,
other: RHS,
m: M,
data: &Self::Data
) -> Self::Output;
}
Expand description
Multiplies two numbers modulo a third number $m$. Assumes the inputs are already reduced mod $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
Required Methods
fn precompute_mod_mul_data(m: &M) -> Self::Data
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
Implementations on Foreign Types
sourceimpl ModMulPrecomputed<u32, u32> for u32
impl ModMulPrecomputed<u32, u32> for u32
sourcefn precompute_mod_mul_data(m: &u32) -> 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.
sourcefn mod_mul_precomputed(self, other: u32, m: u32, data: &u32) -> u32
fn mod_mul_precomputed(self, other: u32, m: u32, data: &u32) -> u32
Multiplies two numbers modulo a third number $m$. Assumes the inputs are 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.
Examples
See here.
This is equivalent to n_mulmod2_preinv
from ulong_extras.h
, FLINT 2.7.1.
type Output = u32
type Data = u32
sourceimpl ModMulPrecomputed<u64, u64> for u64
impl ModMulPrecomputed<u64, u64> for u64
sourcefn precompute_mod_mul_data(m: &u64) -> 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.
sourcefn mod_mul_precomputed(self, other: u64, m: u64, data: &u64) -> u64
fn mod_mul_precomputed(self, other: u64, m: u64, data: &u64) -> u64
Multiplies two numbers modulo a third number $m$. Assumes the inputs are 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.
Examples
See here.
This is equivalent to n_mulmod2_preinv
from ulong_extras.h
, FLINT 2.7.1.
type Output = u64
type Data = u64
sourceimpl ModMulPrecomputed<u8, u8> for u8
impl ModMulPrecomputed<u8, u8> for u8
sourcefn precompute_mod_mul_data(m: &u8) -> u32
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.
sourcefn mod_mul_precomputed(self, other: u8, m: u8, data: &u32) -> u8
fn mod_mul_precomputed(self, other: u8, m: u8, data: &u32) -> u8
Multiplies two numbers modulo a third number $m$. Assumes the inputs are 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.
Examples
See here.
This is equivalent to n_mulmod2_preinv
from ulong_extras.h
, FLINT 2.7.1.
type Output = u8
type Data = u32
sourceimpl ModMulPrecomputed<u16, u16> for u16
impl ModMulPrecomputed<u16, u16> for u16
sourcefn precompute_mod_mul_data(m: &u16) -> u32
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.
sourcefn mod_mul_precomputed(self, other: u16, m: u16, data: &u32) -> u16
fn mod_mul_precomputed(self, other: u16, m: u16, data: &u32) -> u16
Multiplies two numbers modulo a third number $m$. Assumes the inputs are 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.
Examples
See here.
This is equivalent to n_mulmod2_preinv
from ulong_extras.h
, FLINT 2.7.1.
type Output = u16
type Data = u32
sourceimpl ModMulPrecomputed<u128, u128> for u128
impl ModMulPrecomputed<u128, u128> for u128
sourcefn precompute_mod_mul_data(_m: &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.
sourcefn mod_mul_precomputed(self, other: u128, m: u128, _data: &()) -> u128
fn mod_mul_precomputed(self, other: u128, m: u128, _data: &()) -> u128
Multiplies two numbers modulo a third number $m$. Assumes the inputs are 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.
Examples
See here.
This is equivalent to n_mulmod2_preinv
from ulong_extras.h
, FLINT 2.7.1.
type Output = u128
type Data = ()
sourceimpl ModMulPrecomputed<usize, usize> for usize
impl ModMulPrecomputed<usize, usize> for usize
sourcefn precompute_mod_mul_data(m: &usize) -> 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.
sourcefn mod_mul_precomputed(self, other: usize, m: usize, data: &usize) -> usize
fn mod_mul_precomputed(self, other: usize, m: usize, data: &usize) -> usize
Multiplies two numbers modulo a third number $m$. Assumes the inputs are 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.
Examples
See here.
This is equivalent to n_mulmod2_preinv
from ulong_extras.h
, FLINT 2.7.1.