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//! ## Basic usage
16//!
17//! Depending on the modulus, you can choose between two types:
18//!
19//! - [`Residue32`]: for odd moduli up to `2_654_435_769` (~ `2^31.3`)
20//! - [`Residue64`]: for any odd modulus that fits in `u64`
21//!
22//! Since [`Residue32`] is typically faster than [`Residue64`], prefer using it whenever possible.
23//!
24//! ## Advanced usage
25//!
26//! `Residue` types hold a reference to their corresponding `Modulus` for convenience.
27//! However, when storing many residues with the same modulus, this can be memory-intensive.
28//! In such cases, [`Raw32`] or [`Raw64`] can be used instead.
29//! The caller is responsible for associating them with the correct modulus.
30//!
31//! # Example
32//!
33//! Below is an implementation of a rolling hash algorithm using [`Residue64`].
34//! This allows the use of large prime moduli without overflow.
35//!
36//! ```
37#![doc = include_str!("../examples/rolling_hash.rs")]
38//! ```
39#![warn(missing_docs)]
40#![warn(missing_debug_implementations)]
41pub mod factorize;
42pub mod prime;
43
44mod residue32;
45pub use residue32::*;
46
47mod residue64;
48pub use residue64::*;
49
50/// small prime numbers less than 64
51///
52/// `(SELF >> x) & 1 == 1` iff `x` is prime
53const PRIME_LT_64: u64 = {
54 let mut test = u64::MAX << 2;
55 let mut x = 2;
56 while x < 64 {
57 if (test >> x) & 1 == 1 {
58 let mut y = x * x;
59 while y < 64 {
60 test &= !(1 << y);
61 y += x;
62 }
63 }
64
65 x += 1;
66 }
67 test
68};
69
70/// multiples of 2, 3 or 5.
71///
72/// `(SELF >> x % 30) & 1 == 1` iff `x` is coprime to 2, 3, and 5
73const COPRIME_2_3_5: u32 = {
74 let mut table = 0;
75
76 let mut n = 0;
77 while n < 30 {
78 table |= if n % 2 == 0 || n % 3 == 0 || n % 5 == 0 {
79 0 // composite
80 } else {
81 1 // may be prime
82 } << n;
83 n += 1;
84 }
85
86 table
87};