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 const_monty_params! macro can be used to define Montgomery parameters at compile-time from a modulus, whereas the const_monty_form! macro can define a ConstMontyForm constant.

Dynamic moduli chosen at runtime

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

Modules

add 🔒

bingcd 🔒

This module implements (a constant variant of) the Optimized Extended Binary GCD algorithm, which is described by Pornin as Algorithm 2 in “Optimized Binary GCD for Modular Inversion”. Ref: https://eprint.iacr.org/2020/972.pdf

boxed_monty_form 🔒

Implements heap-allocated BoxedMontyForms, supporting modular arithmetic with a modulus set at runtime.

const_monty_form 🔒

Implements ConstMontyForms, supporting modular arithmetic with a constant modulus.

div_by_2 🔒

fixed_monty_form 🔒

Implements MontyForms, supporting modular arithmetic with a modulus set at runtime.

lincomb 🔒

monty_params 🔒

Modulus-specific Montgomery form parameters.

mul 🔒

pow 🔒

prime_params 🔒

Parameter calculation for prime moduli.

reduction 🔒

Modular reduction implementation.

safegcd 🔒

Implementation of Bernstein-Yang modular inversion and GCD algorithm (a.k.a. safegcd) as described in: https://eprint.iacr.org/2019/266.

sqrt 🔒

sub 🔒

Structs

BoxedMontyForm

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

BoxedMontyParams

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

ConstMontyForm

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

FixedMontyForm

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

MontyParams

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

PrimeParams

Parameters for supporting efficient computations on integers in Montgomery form with a prime modulus.

Traits

ConstMontyParams

Trait representing a modulus and its associated constants for converting in and out of Montgomery form.

ConstPrimeMontyParams

Trait representing a prime modulus and its associated constants for converting in and out of Montgomery form.

Retrieve

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

Type Aliases

FixedMontyParams

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