lib-modulo 0.8.0

Fast modular arithmetic
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63

# Fast Modular Arithmetic


[![crate](https://img.shields.io/crates/v/lib_modulo.svg)](https://crates.io/crates/lib_modulo)
[![docs](https://docs.rs/lib_modulo/badge.svg)](https://docs.rs/lib_modulo)
![no_std](https://img.shields.io/badge/no__std-compatible-blue)
![unsafe](https://img.shields.io/badge/unsafe-forbidden-success)

High-performance word-size modular arithmetic using Montgomery and Plantard multiplication.

## Overview


Naive modular multiplication typically requires widening the operands, followed by an expensive division.
This crate avoids division by using:

- Montgomery multiplication
- Plantard multiplication
- Barrett multiplication

These techniques significantly improve performance, especially when the modulus is determined at *runtime*.

## Features


- 🚀 Fast modular multiplication without division
- âš¡ Optimized for 64-bit platforms
- 💡 Supports any runtime-specified odd modulus
- 🧩 `no_std` compatible
- 🔒 `unsafe`-free

| Type           | Modulus                   | Notes                                             |
| -------------- | ------------------------- | ------------------------------------------------- |
| `Modulus32`    | odd,  $\lesssim 2^{31.3}$ | fastest                                           |
| `Modulus32Any` | in $[2, 2^{32})$          | supports even moduli, zero-cost modulus switching |
| `Modulus64`    | odd, fits in `u64`        | supports large moduli                             |

## Example


```rust
use lib_modulo::Modulus32;

let modulus = Modulus32::new((1 << 10) - 1);

// residue of 1025 modulo 1023
let two = modulus.residue(1025);
assert_eq!(two.get(), 2);

assert_eq!(two.pow(10).get(), 1);
```

See more [examples].

[examples]: https://github.com/qdot3/montgomery/tree/master/examples

## Further reading


### Fast modular multiplication algorithms (alphabetical order)


- [Barrett multiplication](https://doi.org/10.1007/3-540-47721-7_24)
- [Montgomery multiplication](https://doi.org/10.1090/s0025-5718-1985-0777282-x)
- [Plantard multiplication](https://thomas-plantard.github.io/pdf/Plantard21.pdf)

### Fast remainder algorithm


- [Lemire's remainder algorithm](https://doi.org/10.1002/spe.2689)