Trait num_modular::Montgomery

source · [−]
pub trait Montgomery: Sized {
    type Inv;
    type Double;
    fn neginv(m: &Self) -> Option<Self::Inv>;
    fn transform(target: Self, m: &Self) -> Self;
    fn reduce(monty: Self::Double, m: &Self, minv: &Self::Inv) -> Self;
    fn add(lhs: &Self, rhs: &Self, m: &Self) -> Self;
    fn sub(lhs: &Self, rhs: &Self, m: &Self) -> Self;
    fn neg(monty: &Self, m: &Self) -> Self;
    fn mul(lhs: &Self, rhs: &Self, m: &Self, minv: &Self::Inv) -> Self;
    fn pow(base: &Self, exp: &Self, m: &Self, minv: &Self::Inv) -> Self;
}
Expand description

Operations of a integer represented in Montgomery form. This data type can be used in place of a normal integer with regard to modular arithmetics.

The generic type T represents the underlying integer representation, and R=2^B will be used as the auxiliary modulus, where B is automatically selected based on the size of T.

Associated Types

The type for inversion of the modulus.

This type is usually the same as Self, but it can be smaller when using Montgomery form on multi-precision integer representations.

The type of integer with double width. It is only used in reduce(), so it’s okay that it’s not actually doubled with

Required methods

Calculate -(m^-1) mod R, return None if the inverse doesn’t exist.

Transform a normal integer into Montgomery form (compute target*R mod m)

Transform a montgomery form back to normal integer (compute monty/R mod m)

Calculate (lhs + rhs) mod m in Montgomery form

Calculate (lhs - rhs) mod m in Montgomery form

Calculate -monty mod m in Montgomery form

Calculate (lhs * rhs) mod m in Montgomery form

Calculate base ^ exp mod m in Montgomery form

Implementations on Foreign Types

Implementors