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

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

Features

• 🚀 Fast modular multiplication without division
• ⚡ Optimized 32-bit and 64-bit implementations
• 🔒 Supports any odd modulus

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.

Further reading

Fast modular multiplication algorithm

• Montgomery multiplication
• Plantard multiplication

Fast remainder algorithm

• https://onlinelibrary.wiley.com/doi/10.1002/spe.2689