Crate num_modular

Expand description

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 MersenneInt.

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:

PreInv: 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
MersenneInt: Specialization of modulo in form 2^P-K

Structs

MersenneInt

An unsigned integer modulo (pseudo) Mersenne primes 2^P - K, it supports P up to 127 and K < 2^(P-1)

MontgomeryInt

An integer represented in Montgomery form.

PreInv

Pre-computation for fast divisibility check.

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.