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

• 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)

• 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.1"

Enable SIMD features (nightly Rust required):

[dependencies]
rma = { version = "0.1", 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;

Modules

berlekamp

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

cuthill_mckee

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

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.