Crate num_modular

This crate provides efficient Modular arithmetic operations for various integer types, including primitive integers and num-bigint. The latter option is enabled optionally.

To achieve fast modular arithmetics, convert integers to any ModularInteger implementation use static new() or associated ModularInteger::convert() functions. Some builtin implementations of ModularInteger includes MontgomeryInt and FixedMersenneInt.

Example code:

use num_modular::{ModularCoreOps, ModularInteger, MontgomeryInt};

// directly using methods in ModularCoreOps
let (x, y, m) = (12u8, 13u8, 5u8);
assert_eq!(x.mulm(y, &m), x * y % m);

// convert integers into ModularInteger
let mx = MontgomeryInt::new(x, &m);
let my = mx.convert(y); // faster than static MontgomeryInt::new(y, m)
assert_eq!((mx * my).residue(), x * y % m);

Comparison of fast division / modular arithmetics

Several fast division / modulo tricks are provided in these crate, the difference of them are listed below:

• PreModInv: pre-compute modular inverse of the divisor, only applicable to exact division
• Barret (to be implemented): pre-compute (rational approximation of) the reciprocal of the divisor, applicable to fast division and modulo
• Montgomery: Convert the dividend into a special form by shifting and pre-compute a modular inverse, only applicable to fast modulo, but faster than Barret reduction
• FixedMersenne: Specialization of modulo in form 2^P-K under 2^127.

Structs

FixedMersenne

A modular reducer for (pseudo) Mersenne numbers 2^P - K as modulus. It supports P up to 127 and K < 2^(P-1)

Montgomery

A modular reducer based on Montgomery form, only supports odd modulus.

Normalized2by1Divisor

Divide a DoubleWord by a prearranged divisor.

Normalized3by2Divisor

Divide a 3-Word by a prearranged DoubleWord divisor.

PreModInv

Pre-computing the modular inverse for fast divisibility check.

PreMulInv1by1

Divide a Word by a prearranged divisor.

PreMulInv2by1

A wrapper of Normalized2by1Divisor that can be used as a Reducer

PreMulInv3by2

A wrapper of Normalized3by2Divisor that can be used as a Reducer

ReducedInt

An integer in a modulo ring

Vanilla

A plain reducer that just use normal Rem operators. It will keep the integer in range [0, modulus) after each operation.

udouble

A double width integer type based on the largest built-in integer type umax (currently u128), and to support double-width operations on it is the only goal for this type.

Traits

DivExact

Utility function for exact division, with precomputed helper values

ModularAbs

Provides a utility function to convert signed integers into unsigned modular form

ModularCoreOps

Core modular arithmetic operations.

ModularInteger

Represents an number defined in a modulo ring ℤ/nℤ

ModularOps

Collection of common modular arithmetic operations

ModularPow

Modular power functions

ModularRefOps

Collection of operations similar to ModularOps, but takes operands with references

ModularSymbols

Math symbols related to modular arithmetics

ModularUnaryOps

Core unary modular arithmetics

Reducer

A modular reducer that can ensure that the operations on integers are all performed in a modular ring.

Type Aliases

FixedMersenneInt

An integer in modulo ring with a fixed (pseudo) Mersenne number as modulus

MontgomeryInt

An integer in modulo ring based on Montgomery form

VanillaInt

An integer in modulo ring based on conventional Rem operations

umax

Alias of the builtin integer type with max width (currently u128)