m61-modulus

Functions for performing arithmetic modulo the 61st Mersenne number. Aimed at testing bignum implementations.

Documentation

https://www.docs.rs/m61-modulus/

License

This project is licensed under either of

• Apache License, Version 2.0 (LICENSE-APACHE)

• MIT License (LICENSE-MIT)

at your option.

lib.rs:

Functions for performing arithmetic modulo the 61st Mersenne number. Aimed at testing bignum implementations.

Usage

The crate comes with a trait M61Reduction and a type [M61]. M61 is an integer in which all arithmetic is performed the 61st Mersenne number, 2^61 - 1.

use m61_modulus::*;

let x = M61::from(1u64 << 61);
let y = M61::from(1u64);

assert_eq!(x, y);

The trait M61Reduction is implemented for unsigned integer slices, providing two functions for reducing the modulo 2^61 - 1, as if they were digits in a bignum implementation.

use m61_modulus::*;

let x = [1u16, 734u16, 24u16].reduce_m61();
let y = M61::from(1) + M61::from(734 << 16) + M61::from(24u64 << 32);

assert_eq!(x, y);

The functions are reduce_m61, which is single-threaded, and reduce_m61_parallelized, which may spawn additional threads.

This crate comes with two features:

• nightly, which enables support for additional nightly-only ISA extensions like AVX512. Disabled by default.
• std, which provides access to the reduce_m61_parallelized function, which requires the Rust standard library. If disabled, this crate will also work on no-std targets. Enabled by default.

Background

This crate is designed around verifying the results of bignum implementations (like num-bigint) in a cheap manner. By repeating an operation using modular arithmetic one can test the results without having to resort to simpler, but slower implementations involving arbitrary-precision arithmetic.

Arithetic modulo the 61st Mersenne number is particulary suitable for this:

• It is a prime number, which means the results distribute well given random input.
• Its difference of one to the next power of two makes calcuations incredibly cheap.