rust-modinverse

寻找模乘法逆元的小型库。还内置了扩展欧几里得算法的实现。

modinverse

计算整数 a 的模乘法逆元 x，使得 ax ≡ 1 (mod m)。

这样的整数可能不存在。如果存在，则此函数将返回包裹在 Some 中的逆元。否则，将返回 None。

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

找到两个整数 a 和 b 的最大公约数，以及两个整数 x 和 y，使得 ax + by 是 a 和 b 的最大公约数（Bézout系数）。

此函数是扩展欧几里得算法的实现。

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