Struct rsa_cortex_m4::arithmetic::Montgomery

pub struct Montgomery<'n, const D: usize, const E: usize> { /* fields omitted */ }

Montgomery representation of $[x]_{n} := x\text{ }(\text{mod }n)$, as $[x \cdot 2^{-32L}]_n$.

This is an additive isomorphism Modular<L>(_, n) -> Montgomery<L>(_, n). "Montgomery multiplication" means the induced ring structure.

The "trick" is that reduction of excess summands after multiplication can be calculated by a simple right shift instead of an actual modular division.

This needs to be balanced by the overhead of applying the additive isomorphism and its inverse, which is negligible in certain situations, e.g., calculating powers with large exponents.

Note: As described in Incomplete reduction in modular arithmetic (2002), it is not necessary to reduce fully modulo n while calculating in the Montegomery representation.

Also, as described in Efficient software implementations of modular exponentiation (2012), using moduli with both the top and bottom bit set is particularly convenient.

Implementations

impl<'n, const D: usize, const E: usize> Montgomery<'n, D, E>

pub fn to_modular(&self) -> Modular<'n, D, E>

pub fn one(&self) -> Self

pub fn power<const F: usize, const G: usize>(
    &self,
    exponent: &Unsigned<F, G>
) -> Self

Trait Implementations

impl<'a, 'n, const D: usize, const E: usize> Add<&'a Montgomery<'n, D, E>> for &'a Montgomery<'n, D, E>

type Output = Montgomery<'n, D, E>

The resulting type after applying the + operator.

fn add(self, summand: Self) -> Self::Output

Performs the + operation.

impl<'a, 'n, const D: usize, const E: usize> AddAssign<&'a Montgomery<'n, D, E>> for Montgomery<'n, D, E>

fn add_assign(&mut self, summand: &'a Self)

Performs the += operation.

impl<'n, const D: usize, const E: usize> Clone for Montgomery<'n, D, E>

fn clone(&self) -> Montgomery<'n, D, E>

Returns a copy of the value.

pub fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<'n, const D: usize, const E: usize> Mul<&'_ Montgomery<'n, D, E>> for &Montgomery<'n, D, E>

type Output = Montgomery<'n, D, E>

The resulting type after applying the * operator.

fn mul(self, other: Self) -> Self::Output

Performs the * operation.

impl<'n, const D: usize, const E: usize> MulAssign<&'_ Montgomery<'n, D, E>> for Montgomery<'n, D, E>

fn mul_assign(&mut self, other: &Self)

Performs the *= operation.

impl<'a, 'n, const D: usize, const E: usize> Sub<&'a Montgomery<'n, D, E>> for &'a Montgomery<'n, D, E>

type Output = Montgomery<'n, D, E>

The resulting type after applying the - operator.

fn sub(self, subtrahend: Self) -> Self::Output

Performs the - operation.

impl<'a, 'n, const D: usize, const E: usize> SubAssign<&'a Montgomery<'n, D, E>> for Montgomery<'n, D, E>

fn sub_assign(&mut self, subtrahend: &'a Self)

Performs the -= operation.