Crate modinverse

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

Functions

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).

modinverse

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