Modular Multiplicative Inverse


The modular multiplicative inverse of an integer a modulo m is an integer x such that $latex a^{-1} equiv x pmod{m}.$

That is, it is the multiplicative inverse in the ring of integers modulo m. This is equivalent to $latex ax equiv aa^{-1} equiv 1 pmod{m}.$

The multiplicative inverse of a modulo m exists if and only if a and m are coprime (i.e., if gcd(a, m) = 1).

Let’s see various ways to calculate Modular Multiplicative Inverse:

1. Brute Force
We can calculate the inverse using a brute force approach where we multiply a with all possible values x and find a x such that $latex ax equiv 1 pmod{m}.$ Here’s a sample C++ code:

The time complexity of the above codes is O(m).

2. Using Extended Euclidean Algorithm
We have to find a number x such that a·x = 1 (mod m). This can be written as well…

View original post 985 more words


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s