Crate modicum

Modular arithmetic

This crate provides a set of traits to perform modular arithmetic on integer types. The traits are implemented for the standard integer types and can be implemented for custom integer types. The traits are:

• Constrain<M>: constrain an integer to a modulus.
• AddMod<M>: add two integers and constrain the result to a modulus.
• SubMod<M>: subtract two integers and constrain the result to a modulus.
• MulMod<M>: multiply two integers and constrain the result to a modulus.
• DivMod<M>: divide two integers and constrain the result to a modulus.
• PowMod<M>: raise an integer to a power and constrain the result to a modulus.
• EqMod<M>: check if two integers are congruent modulo a given modulus.
• Invert: invert an integer with respect to a modulus.

Example

use modicum::*;
use pretty_assertions::assert_eq;

let a = 5_i8;
let b = 3_i8;
let modulus = 7_u32;
assert_eq!(a.add_mod(b, modulus), 1);
assert_eq!(a.sub_mod(b, modulus), 2);
assert_eq!(a.mul_mod(b, modulus), 1);
assert_eq!(a.div_mod(b, modulus), Some(4));
assert!(a.eq_mod(5, modulus));
assert!(!a.ne_mod(5, modulus));
assert!(a.ne_mod(6, modulus));
assert!(!a.eq_mod(6, modulus));

Traits

• AddMod
  A trait to add two integers and constrain the result to a modulus.
• Constrain
  A trait to constrain an integer to a modulus.
• DivMod
  A trait to divide two integers and constrain the result to a modulus.
• Egcd
  A trait to compute the extended greatest common divisor of two integers.
• EqMod
  A trait to check if two integers are congruent, that is, they are equal modulo a given modulus.
• Integer
  A trait for integers.
• Invert
  A trait to invert an integer modulo a modulus.
• Modulus
  Modulus is an unsigned integer that can be cast to some other type T. The purpose is to restrict the modulus to unsigned integers yet allow calculations with signed integers when necessary.
• MulMod
  A trait to multiply two integers and constrain the result to a modulus.
• PowMod
  A trait to raise an integer to a power and constrain the result to a modulus.
• SubMod
  A trait to subtract two integers and constrain the result to a modulus.