lib_modulo/lib.rs
1//! # Fast modular arithmetic
2//!
3//! Provides efficient types for modular arithmetic.
4//!
5//! Naive modular multiplication typically requires widening the operands
6//! followed by an expensive division.
7//! This crate avoids division by using [Montgomery] or [Plantard] multiplication,
8//! enabling faster modular operations.
9//!
10//! [Plantard]: https://thomas-plantard.github.io/pdf/Plantard21.pdf
11//! [Montgomery]: https://doi.org/10.1090/s0025-5718-1985-0777282-x
12//!
13//! # Guide
14//!
15//! Depending on the modulus, you can choose between two types:
16//!
17//! - [`Residue32`]: for odd moduli up to `2_654_435_769` (~ `2^31.3`)
18//! - [`Residue64`]: for any odd modulus that fits in `u64`
19//!
20//! Since [`Residue32`] is typically faster than [`Residue64`], prefer using it whenever possible.
21//!
22//! # Example
23//!
24//! Below is an implementation of a rolling hash algorithm using [`Residue64`].
25//! This allows the use of large prime moduli without overflow.
26//!
27//! ```
28#![doc = include_str!("../examples/rolling_hash.rs")]
29//! ```
30pub mod factorize;
31pub mod prime;
32
33mod residue32;
34pub use residue32::*;
35
36mod residue64;
37pub use residue64::*;