Crate lib_modulo 

Fast modular arithmetic

Provides efficient types for modular arithmetic.

Naive modular multiplication typically requires widening the operands followed by an expensive division. This crate avoids division by using Montgomery or Plantard multiplication, enabling faster modular operations.

Guide

Basic usage

Depending on the modulus, you can choose between two types:

• Residue32: for odd moduli up to 2_654_435_769 (~ 2^31.3)
• Residue64: for any odd modulus that fits in u64

Since Residue32 is typically faster than Residue64, prefer using it whenever possible.

Advanced usage

Residue types hold a reference to their corresponding Modulus for convenience. However, when storing many residues with 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::Modulus64;
use rand::random_range;

fn main() {
    let src = b"Rust is fast, safe and memory-efficient.";

    // 9th Mersenne number
    let modulus = Modulus64::new((1 << 61) - 1);
    let base = modulus.residue(random_range(2..(1 << 61) - 1));

    // hash[i] = hash(src[..i])
    let hash = {
        let mut hash = Vec::with_capacity(src.len() + 1);
        hash.push(modulus.residue(0));

        for (i, s) in src.into_iter().enumerate() {
            hash.push(hash[i] * base + modulus.residue(*s as u64));
        }

        hash
    };

    let contains = |key: &[u8]| {
        let hashed_key = key.iter().fold(modulus.residue(0), |hash, s| {
            hash * base + modulus.residue(*s as u64)
        });

        let coef = base.pow(key.len() as u64);
        for i in key.len()..hash.len() {
            if hashed_key == hash[i] - hash[i - key.len()] * coef {
                return true;
            }
        }
        false
    };

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

    // `src` does not contain these
    assert!(!contains(b"slow"));
    assert!(!contains(b"inconvenient"));
    assert!(!contains(b"compilation is slow"));
}

Modules

factorize

prime

Structs

Modulus32

Factory of Residue32.

Modulus64

Factory of Residue64.

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.