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