Let $$a,b\in\mathbb{Z}$$ be positive integers $a,b\in\mathbb Z$ with $$a\le b$$ which are co-prime. The algorithm $$\operatorname{invmod}(a,b)$$ calculates correctly the multiplicative inverse $a^{-1}$ in the ring of congruences $\mathbb Z_b,$ i.e. for which $$a\cdot a^{-1}\equiv 1\mod b.$$ In particular, if $b=p$ is a prime number, this is the unique inverse of $a$ modulo $b$ in the field of congruences $\mathbb Z_p.$

The algorithm requires $$\mathcal O(\log |b|)$$ (worst case and average case) division operations, which corresponds to $$\mathcal O(\log^2 |b|)$$ bit operations.

Algorithm: Calculation of Inverses Modulo a Number (Python)

def invmod(a, b): res = gcdext(a, b) if res[^0] != 1: raise NotCoPrimeException(a, b) else: if res[^1] < 0: res[^1] = res[^1] + (abs(res[^1]) // b + 1) * b return res[^1]

Usage

print(invmod(16, 21))

1. will output
2. will output

Proofs: 1

Propositions: 1

Thank you to the contributors under CC BY-SA 4.0!

Github:

References

Bibliography

1. Hermann, D.: "Algorithmen Arbeitsbuch", Addison-Wesley Publishing Company, 1992
2. BlĂ¶mer, J.: "Lecture Notes Algorithmen in der Zahlentheorie", Goethe University Frankfurt, 1997