### 17 releases

0.6.1 | Aug 31, 2023 |
---|---|

0.5.1 | May 30, 2022 |

0.2.1 | Mar 30, 2022 |

#**46** in Math

**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

. Note that this crate also supports `num-bigint`

. To enable `[``no_std``]`

related functionalities, enable the `std`

feature of the crate.`std`

###
`lib.rs`

:

This crate provides efficient Modular arithmetic operations for various integer types,
including primitive integers and

. The latter option is enabled optionally.`num-bigint`

To achieve fast modular arithmetics, convert integers to any [ModularInteger] implementation
use static

or associated [ModularInteger::convert()] functions. Some builtin implementations
of [ModularInteger] includes [MontgomeryInt] and [FixedMersenneInt].`new``(``)`

Example code:

`use` `num_modular``::``{`ModularCoreOps`,` ModularInteger`,` MontgomeryInt`}``;`
`//` directly using methods in ModularCoreOps
`let` `(`x`,` y`,` m`)` `=` `(``12``u8``,` `13``u8``,` `5``u8``)``;`
`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

under 2^127.`2``^`P`-`K

#### Dependencies

~120KB