#math #rsa #integer #inverse

modinverse

Small library for finding the modular multiplicative inverses

2 releases

Uses old Rust 2015

0.1.1 Dec 8, 2018
0.1.0 Feb 8, 2017

#959 in Cryptography

Download history 295/week @ 2022-08-14 804/week @ 2022-08-21 881/week @ 2022-08-28 537/week @ 2022-09-04 783/week @ 2022-09-11 562/week @ 2022-09-18 481/week @ 2022-09-25 803/week @ 2022-10-02 526/week @ 2022-10-09 331/week @ 2022-10-16 1083/week @ 2022-10-23 325/week @ 2022-10-30 348/week @ 2022-11-06 272/week @ 2022-11-13 505/week @ 2022-11-20 559/week @ 2022-11-27

1,724 downloads per month
Used in 5 crates

Unlicense

5KB

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.

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.

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

Dependencies

~200KB