rust-modinverse

Small library for finding the modular multiplicative inverses. Also has an implementation of the extended Euclidean algorithm built in.

egcd

Implementation of the extended Euclidean algorithm.

The first argument should be smaller than the second. This is checked with an assert!().

```rust use modinverse::egcd;

let smaller = 3; let larger = 26; let (g, x, y) = egcd(smaller, larger);

asserteq!(g, 1); // Greatest common denominator asserteq!(x, 9); // Bézout coefficient x asserteq!(y, -1); // Bézout coefficient y asserteq!((smaller * x) + (larger * y), g); // Make sure it all works out according to plan ```

modinverse

Function to calculate the modular multiplicative inverse of an integer a modulo m.

A modular multiplicative inverse may not exist. If that is the case, this function will return None. Otherwise, the inverse will be returned wrapped up in a Some.

```rust use modinverse::modinverse;

let doesexist = modinverse(3, 26); let doesnot_exist = modinverse(4, 32);

match doesexist { Some(i) => asserteq!(i, 9), None => panic!("modinverse() didn't work as expected"), }

match doesnotexist { Some(i) => panic!("modinverse() found an inverse when it shouldn't have"), None => {}, } ```