Quickly Computing Inverses and Huge Powers

This section is about how to solve the equation $ax\equiv 1\pmod{n}$ when we know it has a solution, and how to efficiently compute $a^m\pmod{n}$ . We also discuss a simple probabilistic primality test that relies on our ability to compute $a^m\pmod{n}$ quickly. All three of these algorithms are of fundamental importance to the cryptography algorithms of Chapter 3.