lib_modulo/lib.rs
1/*!
2# Fast Modular Arithmetic
3
4[](https://crates.io/crates/lib_modulo)
5[](https://docs.rs/lib_modulo)
6
7
8
9High-performance word-size modular arithmetic using Barrett, Montgomery or Plantard multiplication.
10
11# Overview
12
13Naive modular multiplication typically requires widening the operands, followed by an expensive division.
14This crate avoids division by using:
15
16- [Barrett multiplication](https://doi.org/10.1007/3-540-47721-7_24)
17- [Montgomery multiplication](https://doi.org/10.1090/s0025-5718-1985-0777282-x)
18- [Plantard multiplication](https://thomas-plantard.github.io/pdf/Plantard21.pdf)
19
20These techniques significantly improve performance, especially when the modulus is determined at *runtime*.
21
22# Selection guide
23
24| Type | Modulus | Notes |
25|------------------|---------------------|----------------------------------------------------|
26| [`Modulus32`] | odd, < 2^31.3... | fastest |
27| [`Modulus32Any`] | in `[2, 2^32)` | supports even moduli, zero-cost modulus switching |
28| [`Modulus64`] | odd, fits in `u64` | supports large moduli |
29
30# Advanced usage
31
32`Residue{N}` types hold a reference to their corresponding `Modulus{N}` for convenience.
33However, when storing many residues sharing the same modulus, this can be memory-intensive.
34
35In such cases, [`Raw32`] or [`Raw64`] can be used instead.
36The caller is responsible for associating them with the correct modulus.
37
38# Example
39
40Below is an implementation of a rolling hash algorithm using [`Residue64`].
41This allows the use of large prime moduli without overflow.
42
43```
44*/
45#![doc = include_str!("../examples/rolling_hash.rs")]
46//! ```
47#![warn(missing_docs)]
48#![warn(missing_debug_implementations)]
49#![warn(clippy::all)]
50#![warn(clippy::cargo)]
51#![forbid(unsafe_code)]
52#![no_std]
53
54mod residue32;
55pub use residue32::*;
56
57mod residue32any;
58pub use residue32any::*;
59
60mod residue64;
61pub use residue64::*;
62
63mod prime;
64pub use prime::*;