Struct rsa_cortex_m4::numbers::Convenient

#[repr(transparent)]pub struct Convenient<const D: usize, const E: usize>(_);

Unsigned numbers with both their top and bottom bits set – highly convenient for modular arithmetic!

In particular, they are odd. But also, $n \ge 2^{m - 1}$, with strict inequality by oddness.

As described in Incomplete reduction in modular arithmetic (2002), it is not necessary to reduce fully modulo n while calculating modular arithmetic. Instead, we can reduce modulo $2^m$, and only "fully" reduce when so desired.

Their arguments apply to non-prime moduli also, and the "convenient" ones have the properties, in their terminology, that $I = 1$ and $J = 2$, hence $F = 2^m - p$ and $G = 2p - 2^m$. Moreover (!!!), the last case/reduction in their modular addition / subtraction never occurs.

E.g., in addition, we have $F = 2^m - n < 2^m - 2^{m - 1} = 2^{m-1}$, and so $T := S + F < (2^m - 2) + 2^{m - 1} < 2^{m - 1}$.

Implementations

impl<const D: usize, const E: usize> Convenient<D, E>

pub fn as_odd(&self) -> &Odd<D, E>

pub fn into_odd(self) -> Odd<D, E>

pub fn as_unsigned(&self) -> &Unsigned<D, E>

pub fn into_unsigned(self) -> Unsigned<D, E>

Methods from Deref<Target = Unsigned<D, E>>

pub fn checked_add(&self, summand: &Self) -> Option<Self>

pub fn wrapping_add_assign(&mut self, summand: &Self)

pub fn wrapping_add(&self, summand: &Self) -> Self

pub fn wrapping_neg(&self) -> Self

pub fn checked_sub(&self, subtrahend: &Self) -> Option<Self>

pub fn wrapping_sub_assign<T: Number>(&mut self, subtrahend: &T)

pub fn wrapping_sub(&self, subtrahend: &Self) -> Self

pub fn wrapping_mul(&self, factor: &Self) -> Self

pub fn wrapping_inv(&self) -> Result<Self>

The wrapping inverse, i.e., the exact inverse w.r.t wrapping multiplication.

Exists if and only if the number is odd.

This uses $\mathcal{O}(\log n)$ loops in Self::BITS, very efficient (!)

Source: Fig. 1 from GCD-Free Algorithms for Computing Modular Inverses (2003)

Note that this source is highly confusing! What they mean to say is to iterate $y \leftarrow y(2 - ey)$ in $\mathbb{Z}/2^{|f|}$, where the output is an inverse of $e$ modulo $2^{2i}$. In other words, the $\text{mod }2^i$ is a typo, and should be $\text{mod }2^{|f|}$.

cf. also Crypto StackExchange.

pub fn modulo<'n, const F: usize, const G: usize>(
    &self,
    n: &'n Convenient<F, G>
) -> Modular<'n, F, G>

The associated residue class modulo n.

Note that storage requirements of the residue class are the same as the modulus (+ reference to it), not the original integer.

This uses incomplete reduction ([Self::partially_reduce]) for efficiency.

pub fn modulo_prime<'p, const F: usize, const G: usize>(
    &self,
    p: &'p Prime<F, G>
) -> PrimeModular<'p, F, G>

pub fn reduce<const F: usize, const G: usize>(
    &self,
    n: &Unsigned<F, G>
) -> Unsigned<F, G>

The canonical (completely) reduced representative of the associated residue class modulo $n$.

Cf. Modular.

pub const fn digit(&self) -> Digit

pub fn to_bytes(&self) -> BigEndian<D, E, 1>

Return buffer that dereferences as big-endian bytes.

pub fn leading_digit(&self) -> Option<Digit>

pub fn significant_digits(&self) -> &[Digit]

pub fn to_unsigned<const M: usize, const N: usize>(
    &self
) -> Result<Unsigned<M, N>>

Trait Implementations

impl<const D: usize, const E: usize> AsRef<Convenient<D, E>> for Prime<D, E>

fn as_ref(&self) -> &Convenient<D, E>

Performs the conversion.

impl<const D: usize, const E: usize> AsRef<Unsigned<D, E>> for Convenient<D, E>

fn as_ref(&self) -> &Unsigned<D, E>

Performs the conversion.

impl<const D: usize, const E: usize> Clone for Convenient<D, E>

fn clone(&self) -> Convenient<D, E>

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<const D: usize, const E: usize> Debug for Convenient<D, E>

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<const D: usize, const E: usize> Deref for Convenient<D, E>

type Target = Unsigned<D, E>

The resulting type after dereferencing.

fn deref(&self) -> &Self::Target

Dereferences the value.

impl<const D: usize, const E: usize> DerefMut for Convenient<D, E>

fn deref_mut(&mut self) -> &mut Self::Target

Mutably dereferences the value.

impl<const D: usize, const E: usize> From<Convenient<D, E>> for Unsigned<D, E>

fn from(convenient: Convenient<D, E>) -> Self

Performs the conversion.

impl<T, const D: usize, const E: usize> PartialEq<T> for Convenient<D, E> where
    T: Number, 

fn eq(&self, other: &T) -> bool

This method tests for self and other values to be equal, and is used by ==.

#[must_use]pub fn ne(&self, other: &Rhs) -> bool

This method tests for !=.

impl<const D: usize, const E: usize> RefCast for Convenient<D, E>

type From = Odd<D, E>

fn ref_cast(_from: &Self::From) -> &Self

fn ref_cast_mut(_from: &mut Self::From) -> &mut Self

impl<const D: usize, const E: usize> TryFrom<Unsigned<D, E>> for Convenient<D, E>

type Error = Error

The type returned in the event of a conversion error.

fn try_from(unsigned: Unsigned<D, E>) -> Result<Self>

Enforces odd parity.