Crate rma

R-Math Algorithms

A Rust crate for rare, high-performance mathematical algorithms not commonly found in mainstream libraries aimed for practical use.

Features

• Chakravala: Solves Pell’s equation x² - d*y² = 1 for a given non-square integer d.
• Berlekamp’s Algorithm: Factorization of polynomials over finite fields (GF(p))
• Tonelli-Shanks: Modular square roots (r^2 ≡ n mod p) over prime moduli (constant-time version)
• Cuthill-McKee & Reverse Cuthill-McKee: Bandwidth reduction for sparse symmetric matrices (adjacency list, CSR, and CSC formats)
  • Supports conversion from sprs sparse matrix types
• Freivalds’ Algorithm: Fast probabilistic verification of matrix multiplication (scalar, modular, and SIMD-accelerated variants)
• Fast Minimum Degree Algorithm: Exact elimination ordering for sparse matrices with O(nm) complexity
  • First algorithm to improve on the naive O(n³) approach (Cummings et al., 2020)
  • Achieves output-sensitive bounds of O(min{m√m*, Δm*} log n)
  • Based on breakthrough theoretical results from Cummings, Fahrbach, and Fatehpuria
• Well-documented, tested, and benchmarked implementations
• SIMD acceleration for Freivalds’ algorithm (nightly Rust required, simd feature)
• no_std compatible (except for benchmarks and RNG)

Usage

Add to your Cargo.toml:

[dependencies]
rma = "0.4"

Enable SIMD features (nightly Rust required):

[dependencies]
rma = { version = "0.4", features = ["simd"] }

SIMD Feature

• The simd feature enables SIMD-accelerated Freivalds’ algorithm. Requires nightly Rust and the portable_simd feature.
• On stable Rust, only scalar and modular versions are available.

Examples

See the documentation for each algorithm.

License

Licensed under either of

• Apache License, Version 2.0
• MIT license

Re-exports

pub use freivalds::freivalds_verify_scalar;

pub use freivalds::freivalds_verify_scalar_mod;

pub use cuthill_mckee::CscMatrix;

pub use cuthill_mckee::CsrMatrix;

pub use cuthill_mckee::cuthill_mckee;

pub use cuthill_mckee::cuthill_mckee_csc;

pub use cuthill_mckee::cuthill_mckee_csr;

pub use cuthill_mckee::reverse_cuthill_mckee;

pub use cuthill_mckee::reverse_cuthill_mckee_csc;

pub use cuthill_mckee::reverse_cuthill_mckee_csr;

pub use tonelli_shanks::TonelliShanksError;

pub use tonelli_shanks::tonelli_shanks_ct;

pub use chakravala::chakravala;

pub use fast_minimum_degree::fast_minimum_degree;

pub use fast_minimum_degree::fast_minimum_degree_with_stats;

pub use fast_minimum_degree::FastMinimumDegreeError;

Modules

berlekamp

Berlekamp’s Root Finding Algorithm for polynomials over finite fields (prime fields).

chakravala

Chakravala method for solving Pell’s equation x² - d*y² = 1.

cuthill_mckee

Cuthill–McKee and Reverse Cuthill–McKee (RCM) algorithm for bandwidth reduction of sparse symmetric matrices.

fast_minimum_degree

Fast Minimum Degree Algorithm for producing exact elimination orderings.

freivalds

Freivalds’ algorithm for fast probabilistic matrix multiplication verification.

tonelli_shanks

Tonelli–Shanks algorithm for modular square roots (r^2 ≡ n mod p) over prime moduli. Constant-time version.