# Crate m61_modulus

source ·## Expand description

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.

## Structs

- A 64-bit integer in which arithmetic is performed modulp
`2^61 - 1`

.

## Traits

- Helper trait for making the fuctions accessible using the dot operator.