◀ ▲ ▶Branches / Theoretical-computer-science / Semi-numerical-algorithms / Proof

Proof

(related to Algorithm: Calculation of Inverses Modulo a Number (Python))

• The algorithm uses gcdext to calculate the numbers $x,y$ with $ax+by=\gcd(a,b).$
• If $\gcd(a,b)=1$, the value of $x$ is an integer fulfilling $ax\equiv 1\mod b.$
• Otherwise, an exception is thrown, since a multiplicative inverse does not exist.
• In the last step, if $x < 0,$ $\operatorname{invmod}$ choses a positive representative of the same congruence class modulo $b$ in the time $\mathcal O(1).$
• Altogether, the runtime is the same as in the gcdext algorithm, i.e. $\mathcal O(b).$
  ∎

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