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](https://en.wikipedia.org/wiki/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 does_exist = modinverse(3, 26);
let does_not_exist = modinverse(4, 32);
match does_exist {
Some(x) => assert_eq!(x, 9),
None => panic!("modinverse() didn't work as expected"),
}
match does_not_exist {
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](https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm).
```rust
use modinverse::egcd;
let a = 26;
let b = 3;
let (g, x, y) = egcd(a, b);
assert_eq!(g, 1);
assert_eq!(x, -1);
assert_eq!(y, 9);
assert_eq!((a * x) + (b * y), g);
```