rust-modinverse

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

modinverse

Calculates the modular multiplicative inverse x of an integer a such that ax ≡ 1 (mod m).

Such an integer may not exist. If so, 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(x) => asserteq!(x, 9), None => panic!("modinverse() didn't work as expected"), }

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

egcd

Finds the greatest common denominator of two integers a and b, and two integers x and y such that ax + by is the greatest common denominator of a and b (Bézout coefficients).

This function is an implementation of the extended Euclidean algorithm.

```rust use modinverse::egcd;

let a = 26; let b = 3; let (g, x, y) = egcd(a, b);

asserteq!(g, 1); asserteq!(x, -1); asserteq!(y, 9); asserteq!((a * x) + (b * y), g); ```