Fast Modular Arithmetic

High-performance word-size modular arithmetic using Montgomery and Plantard multiplication.

Overview

Naive modular multiplication typically requires widening the operands, followed by an expensive division. This crate avoids division by using:

Montgomery multiplication
Plantard multiplication
Barrett multiplication

These techniques significantly improve performance, especially when the modulus is determined at runtime.

Features

🚀 Fast modular multiplication without division
⚡ Optimized for 64-bit platforms
💡 Supports any runtime-specified odd modulus
🧩 no_std compatible
🔒 unsafe-free

Type	Modulus	Notes
`Modulus32`	odd, $\lesssim 2^{31.3}$	fastest
`Modulus32Any`	in $[2, 2^{32})$	supports even moduli, zero-cost modulus switching
`Modulus64`	odd, fits in `u64`	supports large moduli

Example

use lib_modulo::Modulus32;

let modulus = Modulus32::new((1 << 10) - 1);

// residue of 1025 modulo 1023
let two = modulus.residue(1025);
assert_eq!(two.get(), 2);

assert_eq!(two.pow(10).get(), 1);

See more examples.

lib-modulo 0.8.1

Fast Modular Arithmetic

Overview

Features

Example

Further reading

Fast modular multiplication algorithms (alphabetical order)

Fast remainder algorithm