## no-std num-modular

Implementation of efficient integer division and modular arithmetic operations with generic number types. Supports various backends including num-bigint, etc

### 17 releases

 0.6.1 Aug 31, 2023 May 30, 2022 Mar 30, 2022

#46 in Math

Used in 38 crates (11 directly)

Apache-2.0

145KB
3.5K SLoC

# num-modular

A generic implementation of integer division and modular arithmetics in Rust. It provide basic operators and an type to represent integers in a modulo ring. Specifically the following features are supported:

• Common modular arithmetics: `add`, `sub`, `mul`, `div`, `neg`, `double`, `square`, `inv`, `pow`
• Optimized modular arithmetics in Montgomery form
• Optimized modular arithmetics with pseudo Mersenne primes as moduli
• Fast integer divisibility check
• Legendre, Jacobi and Kronecker symbols

It also support various integer type backends, including primitive integers and `num-bigint`. Note that this crate also supports `[no_std]`. To enable `std` related functionalities, enable the `std` feature of the crate.

### `lib.rs`:

This crate provides efficient Modular arithmetic operations for various integer types, including primitive integers and `num-bigint`. The latter option is enabled optionally.

To achieve fast modular arithmetics, convert integers to any [ModularInteger] implementation use static `new()` or associated [ModularInteger::convert()] functions. Some builtin implementations of [ModularInteger] includes [MontgomeryInt] and [FixedMersenneInt].

Example code:

``````use num_modular::{ModularCoreOps, ModularInteger, MontgomeryInt};

// directly using methods in ModularCoreOps
let (x, y, m) = (12u8, 13u8, 5u8);
assert_eq!(x.mulm(y, &m), x * y % m);

// convert integers into ModularInteger
let mx = MontgomeryInt::new(x, &m);
let my = mx.convert(y); // faster than static MontgomeryInt::new(y, m)
assert_eq!((mx * my).residue(), x * y % m);
``````

# Comparison of fast division / modular arithmetics

Several fast division / modulo tricks are provided in these crate, the difference of them are listed below:

• [PreModInv]: pre-compute modular inverse of the divisor, only applicable to exact division
• Barret (to be implemented): pre-compute (rational approximation of) the reciprocal of the divisor, applicable to fast division and modulo
• [Montgomery]: Convert the dividend into a special form by shifting and pre-compute a modular inverse, only applicable to fast modulo, but faster than Barret reduction
• [FixedMersenne]: Specialization of modulo in form `2^P-K` under 2^127.

~120KB