Module modular

Modular arithmetic support.

This module provides support for various modular arithmetic operations, implemented in terms of Montgomery form.

Constant moduli

The ConstMontyForm and ConstMontyParams types implement support for modular arithmetic where the modulus is fixed at compile-time.

The impl_modulus! macro can be used to define a compile-time modulus, whereas the const_monty_form! macro can define a ConstMontyForm constant.

Dynamic moduli chosen at runtime

The MontyForm and MontyParams types implement support for modular arithmetic where the modulus can vary at runtime.

Structs

BoxedMontyFormalloc

An integer in Montgomery form represented using heap-allocated limbs.

BoxedMontyParamsalloc

Parameters to efficiently go to/from the Montgomery form for an odd modulus whose size and value are both chosen at runtime.

BoxedSafeGcdInverteralloc

Modular multiplicative inverter based on the Bernstein-Yang method.

ConstMontyForm

An integer in Montgomery form modulo MOD, represented using LIMBS limbs. The modulus is constant, so it cannot be set at runtime.

ConstMontyFormInverter

Bernstein-Yang inverter which inverts ConstMontyForm types.

MontyForm

An integer in Montgomery form represented using LIMBS limbs. The odd modulus is set at runtime.

MontyFormInverter

Bernstein-Yang inverter which inverts MontyForm types.

MontyParams

Parameters to efficiently go to/from the Montgomery form for an odd modulus provided at runtime.

SafeGcdInverter

Modular multiplicative inverter based on the Bernstein-Yang method.

Traits

ConstMontyParams

The parameters to efficiently go to and from the Montgomery form for a given odd modulus.

Retrieve

A generalization for numbers kept in optimized representations (e.g. Montgomery) that can be converted back to the original form.

Functions

montgomery_reduction

Algorithm 14.32 in Handbook of Applied Cryptography https://cacr.uwaterloo.ca/hac/about/chap14.pdf