#modular-arithmetic #modular #montgomery #number-theory #arithmetic-operations

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
0.5.1 May 30, 2022
0.2.1 Mar 30, 2022

#46 in Math

Download history 11023/week @ 2024-02-21 11694/week @ 2024-02-28 10540/week @ 2024-03-06 11761/week @ 2024-03-13 11044/week @ 2024-03-20 12544/week @ 2024-03-27 14931/week @ 2024-04-03 15470/week @ 2024-04-10 17919/week @ 2024-04-17 19844/week @ 2024-04-24 23191/week @ 2024-05-01 22171/week @ 2024-05-08 21474/week @ 2024-05-15 18384/week @ 2024-05-22 28886/week @ 2024-05-29 22047/week @ 2024-06-05

96,339 downloads per month
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.

Dependencies

~120KB