Modular Inverses

If you do not have the idea of GCD, please do not read this post first. Please read about GCD in order to understand Modular Inverse.

In GCD, I have concluded that [ gcd(n,m) = a*n + b*m ]. If we have the condition that gcd(n,m)=1, then we can solve the modular inverse.

Below is the algorithm.
1. Write down 2 numbers, n and m. Also the vectors (1,0) and (0,1).
2. Reduce the larger to smaller one.
3. Apply the same computation to vectors.
4. Repeat until we have the number 1 and 0.
5. Preceding result will be the modular inverse.

You might still be wondering why we are doing GCD and Modular Inverse. The reason is it allows us to have a function that we can use for encryption and decryption. One of the example is Merkle–Hellman knapsack cryptosystem.