Function libplayrsa::primes::invmod [−][src]
Expand description
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.
‘’’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 ‘’’