Modular multiplicative inverse
From Wikipedia, the free encyclopedia
The modular multiplicative inverse of an integer a modulo m is an integer x such that
That is, it is the multiplicative inverse in the ring of integers modulo m. This is equivalent to
The multiplicative inverse of a modulo m exists iff a and m are coprime (i.e., if gcd(a, m) = 1). If the modular multiplicative inverse of a modulo m exists, the operation of division by a modulo m can be defined as multiplying by the inverse, which is in essence the same concept as division in the set of reals.
Contents |
[edit] Explanation
When the inverse exists, it is always unique in Zm where m is the modulus. Therefore, the x that is selected as the modular multiplicative inverse is generally a member of Zm for most applications.
For example,
yields
The smallest x that solves this congruence is 4; therefore, the modular multiplicative inverse of 3 (mod 11) is 4. However, another x that solves the congruence is 15 (easily found by adding m, which is 11, to the found inverse).
[edit] Computation
[edit] Extended Euclidean Algorithm
The modular multiplicative inverse of a modulo m can be found with the extended Euclidean algorithm. The algorithm finds solutions to Bézout's identity
where a, b are given and x, y, and gcd(a, b) are the integers that the algorithm discovers. So, since the modular multiplicative inverse is the solution to
by the definition of congruence, m | ax - 1. By definition of divides, this means that
Rearranging produces
with a and m given, x the inverse, and q an integer multiple that will be discarded. This is the exact form of equation that the extended Euclidean algorithm solves -- the only difference being that gcd(a, m)=1 is predetermined instead of discovered. Thus, the modular multiplicative inverse needs to be coprime to the modulus, or the inverse won't exist. The inverse is x, and q is discarded.
This algorithm runs in time O(log(m)2), assuming |a|<m, and is generally more efficient than exponentiation.
[edit] Direct Modular Exponentiation
The direct modular exponentiation method, as an alternative to the extended Euclidean algorithm, is as follows:
According to Euler's theorem, if a is coprime to m, that is, gcd(a, m) = 1, then
where φ(m) is Euler's totient function. This follows from the fact that a belongs to the multiplicative group (Z/mZ)* iff a is coprime to m. Therefore the modular multiplicative inverse can be found directly:
This method is generally slower than the extended Euclidean algorithm, but is sometimes used when an implementation for modular exponentiation is already available. Some disadvantages of this method include:
- the knowledge of φ(m), whose most efficient computation requires m's factorization.
- exponentiation, which can be implemented more efficiently using modular exponentiation, which is a form of binary exponentiation.
[edit] Implementation in Python
def extGCD(N,D):
x=0; y=1;
u=1; v=0;
a=N; b=D;
while (0 != a):
q = int(b/a);
r = b%a;
m = x - u*q;
n = y - v*q;
b=a; a=r; x=u; y=v; u=m; v=n;
return [x, y, b]
def invMOD(N,D): x,y,b = extGCD(N,D); return b == 1 and ((x+D)%D) or None
[edit] Example
invMOD(0xaa4df5cb14b4c31237f98bd1faf527c283c2d0f3eec89718664ba33f9762907c, 0xfffbbd660b94412ae61ead9c2906a344116e316a256fd387874c6c675b1d587d) == 0x8d6a5c1d7adeae3e94b9bcd2c47e0d46e778bc8804a2cc25c02d775dc3d05b0c
