Crate lib_modulo 

Fast Modular Arithmetic

High-performance word-size modular arithmetic using Barrett, Montgomery or Plantard multiplication.

Overview

Naive modular multiplication typically requires widening the operands, followed by an expensive division. This crate avoids division by using:

• Barrett multiplication
• Montgomery multiplication
• Plantard multiplication

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

Selection guide

Type	Modulus	Notes
Modulus32	odd, < 2^31.3…	fastest
Modulus32Any	in [2, 2^32)	supports even moduli, zero-cost modulus switching
Modulus64	odd, fits in u64	supports large moduli

Advanced usage

Residue{N} types hold a reference to their corresponding Modulus{N} for convenience. However, when storing many residues sharing the same modulus, this can be memory-intensive.

In such cases, Raw32 or Raw64 can be used instead. The caller is responsible for associating them with the correct modulus.

Example

Below is an implementation of a rolling hash algorithm using Residue64. This allows the use of large prime moduli without overflow.

use lib_modulo::{primality_test, Modulus64, Raw64};
use rand::random_range;

struct RollingHash {
    modulus: Modulus64,
    // avoid self-reference
    base: Raw64,

    history: Vec<Raw64>,
}

impl RollingHash {
    pub fn new(source: &[u8], modulus: u64, base: u64) -> Self {
        let modulus = Modulus64::new(modulus);
        let base = modulus.residue(base);

        let mut history = Vec::with_capacity(source.len() + 1);
        // offset
        history.push(modulus.residue(0).into_raw());

        // hash prefixes
        for &c in source.iter() {
            let last = history.last().copied().unwrap();
            // `last` and `base` share the same modulus.
            // `Raw{N}` and `Residue{N}` can interact.
            let next = last * base + modulus.residue(c as u64);
            history.push(next.into_raw());
        }

        Self {
            base: base.into_raw(),
            history,
            modulus,
        }
    }

    pub fn contains(&self, target: &[u8]) -> bool {
        let len = target.len();

        let base = self.base.into_residue(&self.modulus);
        let pow = base.pow(len as u64);

        // hash input
        let target = target.iter().fold(self.modulus.residue(0), |hash, c| {
            hash * base + self.modulus.residue(*c as u64)
        });

        (len..self.history.len()).any(|r| {
            // restore hash of windows
            // all of them share the same modulus
            let sub = self.history[r] - self.history[r - len] * pow;
            sub == target
        })
    }
}

fn main() {
    // generate prime at runtime for safety
    let prime = {
        let mut x = random_range(1 << 63..u64::MAX >> 10 << 10) | 1;
        while !primality_test(x) {
            x += 2
        }
        x
    };

    let rolling_hash = RollingHash::new(
        b"Rust is fast, safe and memory-efficient.",
        prime,
        random_range(2..prime),
    );

    // contains these
    assert!(rolling_hash.contains(b"Rust"));
    assert!(rolling_hash.contains(b"fast"));
    assert!(rolling_hash.contains(b"safe"));
    assert!(rolling_hash.contains(b"memory-efficient"));

    // does not contain these
    assert!(!rolling_hash.contains(b"slow"));
    assert!(!rolling_hash.contains(b"inconvenient"));
    assert!(!rolling_hash.contains(b"compilation is slow")); // 🤔
}

Structs

Modulus32

Factory of Residue32.

Modulus64

Factory of Residue64.

Modulus32Any

A modulus in [2, 2^32), including even values.

Raw32

An internal representation of Residue32 without an associated Modulus32.

Raw64

An internal representation of Residue64 without an associated Modulus64.

Residue32

A residue with an odd modulus not exceeding 2_654_435_769.

Residue64

A residue with an odd modulus that fits in 2^64.

Enums

InvalidModulus

Invalid moduli of Modulus32Any.

Functions

primality_test

Performs deterministic Miller-Rabin primality test.