Modular multiplicative inverse
From Wikipedia, the free encyclopedia
The modular multiplicative inverse of an integer n modulo p is an integer m such that
- n-1 ≡ m (mod p)
That is, it is the multiplicative inverse in the ring of integers modulo p. This is equivalent to
- mn ≡ 1 (mod p)
The multiplicative inverse of n modulo p exists iff n and p are coprime (i.e., if gcd(n, p) = 1).
If the modular multiplicative inverse of n modulo p exists, the operation of division by n modulo p can be defined as multiplying by the inverse.
Contents |
[edit] Explanation
We can sometimes find many values of m for which this congruence is true. The m that is selected as the modular multiplicative inverse is generally the smallest natural m possible (or simply the m which is a member of the set Zn, where n is the modulus).
For example:
- 3-1 ≡ m (mod 11)
gives us
- 3m ≡ 1 (mod 11)
The smallest m that solves this congruence is 4; therefore, the modular multiplicative inverse of 3 (mod 11) is 4. However, another m that solves the congruence is 15 (easily found by adding p, which is 11, to the found inverse).
[edit] Computation
[edit] Extended Euclidean Algorithm
The modular multiplicative inverse of n modulo p can be found with the extended Euclidean algorithm. In particular, calling the extended Euclidean algorithm with n and p as arguments results in a triple (x,y,gcd(n,p)) such that
If gcd(n,p)=1 then it follows that
hence x is the modular inverse of n modulo p. If gcd(n,p)≠ 1 then the modular inverse does not exist. This algorithm runs in time O(log(p)2) (assuming |n|<p).
[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 n is coprime to p, that is, gcd(n, p) = 1, then
- nφ(p) ≡ 1 (mod p)
This follows from Lagrange's theorem and the fact that n belongs to the multiplicative group 
iff n is coprime to p.
Therefore,
- nφ(p)-1 ≡ n-1 (mod p)
where φ(p) is Euler's totient function.
the modular multiplicative inverse of n modulo p can thus be found directly:
- nφ(p)-1 ≡ m (mod p)
In the special case where p is prime,
- φ(p) = p - 1
For composite p, see Euler's totient function.
Binary exponentiation can be used to perform this method efficiently, requiring O(log(p)) modular multiplications. Hence the runtime of this method is O(log(p)3) when the schoolbook method for multiplication is used and O(log(p)2 log(log(p))log(log(log(p)))) when the FFT based multiplication by Strassen is used.
This method is generally slower than the extended Euclidean algorithm, but is sometimes used when an implementation for modular exponentiation is already available.
A disadvantage of this method is that it needs φ(p) because the only efficient known computation of this requires the knowledge of p's factors.
