Function libplayrsa::primes::invmod

pub fn invmod(a: &BigUint, n: &BigUint) -> Option<BigUint>

Returns the multiplicative inverse of a modulo n.

Bézout's identity asserts that a and n are coprime if and only if there exist integers s and t such that ns+at=1 Reducing this identity modulo n gives at=1 \mod n.

Thus the remainder of the division of t by n, is the multiplicative inverse of a modulo n.

Pseudocode

'''text function inverse(a, n) t := 0; newt := 1;
r := n; newr := a;
while newr ≠ 0 quotient := r div newr (t, newt) := (newt, t - quotient * newt) (r, newr) := (newr, r - quotient * newr) if r > 1 then return "a is not invertible" if t < 0 then t := t + n return t '''