A very useful post … helps me very much writing key splitter in c++ .. reference code is taking from http://en.wikipedia.org/wiki/Shamir's_Secret_Sharing

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