## Compute the modular inverse using Extended GCD

When you need to calculate the modular inverse for the large co-prime integers, how do you calculate? In my case, I needed to calculate the modular inverse to get the RSA private key from the given public exponent and RSA modulus. At first, I tried to find it by brute-force search, but it turns out it takes very long time to compute the modular inverse for the large numbers. Finally, It is possible to calculate modular inverse efficiently using extended GCD function.
[Read More]