Modular multiplicative inverse


Modular multiplicative inverse

The modular multiplicative inverse of an integer a modulo m is an integer x such that

a^{-1} \equiv x \pmod{m}.

That is, it is the multiplicative inverse in the ring of integers modulo m. This is equivalent to

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). 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 field of reals.

Contents

Explanation

When the inverse exists, it is always unique in \mathbb{Z}_m where m is the modulus. Therefore, the x that is selected as the modular multiplicative inverse is generally a member of \mathbb{Z}_m for most applications.

For example,

3^{-1} \equiv x \pmod{11}

yields

3x \equiv 1 \pmod{11}

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).

Computation

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

ax + by = \gcd(a, b)\,

where a, b are given and xy, and gcd(ab) are the integers that the algorithm discovers. So, since the modular multiplicative inverse is the solution to

ax \equiv 1 \pmod{m},

by the definition of congruence, m | ax − 1, which means that m is a divisor of ax − 1. This, in turn, means that

ax - 1 = qm.\,

Rearranging produces

ax - qm = 1,\,

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(am) = 1 is predetermined instead of discovered. Thus, a 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.

Using Euler's theorem

As an alternative to the extended Euclidean algorithm, Euler's theorem may be used to compute modular inverse:[1]

According to Euler's theorem, if a is coprime to m, that is, gcd(a, m) = 1, then

a^{\varphi(m)} \equiv 1 \pmod{m}

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:

a^{\varphi(m)-1} \equiv a^{-1} \pmod{m}

In the special case when m is a prime, the modular inverse is given by the above equation as:

\! a^{-1} \equiv a^{m-2} \pmod{m}

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 required knowledge of φ(m), whose most efficient computation requires m's factorization. Factorization is widely believed to be a mathematically hard problem. However, calculating φ(m) is trivial in some common cases such as when m is known to be prime or a power of a prime.
  • exponentiation. Though it can be implemented more efficiently using modular exponentiation, when large values of m are involved this is most efficiently computed with the Montgomery reduction method. This algorithm itself requires a modular inverse mod m, which is what we wanted to calculate in the first place. Without the Montgomery method, we're left with standard binary exponentiation which requires division mod m at every step, a slow operation when m is large. Furthermore, any kind of modular exponentiation is a taxing operation with computational complexity O(log φ(m)) = O(log m).

See also

References


Wikimedia Foundation. 2010.

Look at other dictionaries:

  • Multiplicative inverse — The reciprocal function: y = 1/x. For every x except 0, y represents its multiplicative inverse. In mathematics, a multiplicative inverse or reciprocal for a number x, denoted by 1/x or x−1, is a number which when multiplied by x yields the… …   Wikipedia

  • Modular exponentiation — is a type of exponentiation performed over a modulus. It is particularly useful in computer science, especially in the field of cryptography. Doing a modular exponentiation means calculating the remainder when dividing by a positive integer m… …   Wikipedia

  • Modular arithmetic — In mathematics, modular arithmetic (sometimes called clock arithmetic) is a system of arithmetic for integers, where numbers wrap around after they reach a certain value the modulus. The Swiss mathematician Leonhard Euler pioneered the modern… …   Wikipedia

  • Multiplicative group of integers modulo n — In modular arithmetic the set of congruence classes relatively prime to the modulus n form a group under multiplication called the multiplicative group of integers modulo n. It is also called the group of primitive residue classes modulo n. In… …   Wikipedia

  • Multiplicative order — In number theory, given an integer a and a positive integer n with gcd(a,n) = 1, the multiplicative order of a modulo n is the smallest positive integer k with ak ≡ 1 (mod n). The order of a modulo n is usually written ordn(a), or On(a). Contents …   Wikipedia

  • Additive inverse — In mathematics, the additive inverse, or opposite, of a number a is the number that, when added to a, yields zero. The additive inverse of a is denoted −a. For example, the additive inverse of 7 is −7, because 7 + (−7) = 0, and the additive… …   Wikipedia

  • List of mathematics articles (M) — NOTOC M M estimator M group M matrix M separation M set M. C. Escher s legacy M. Riesz extension theorem M/M/1 model Maass wave form Mac Lane s planarity criterion Macaulay brackets Macbeath surface MacCormack method Macdonald polynomial Machin… …   Wikipedia

  • Extended Euclidean algorithm — The extended Euclidean algorithm is an extension to the Euclidean algorithm for finding the greatest common divisor (GCD) of integers a and b : it also finds the integers x and y in Bézout s identity: ax + by = gcd(a, b). ,(Typically either x or… …   Wikipedia

  • RSA — In cryptography, RSA is an algorithm for public key cryptography. It is the first algorithm known to be suitable for signing as well as encryption, and one of the first great advances in public key cryptography. RSA is widely used in electronic… …   Wikipedia

  • Method of successive substitution — In modular arithmetic, the method of successive substitution is a method of solving problems of simultaneous congruences by using the definition of the congruence equation. It is commonly applied in cases where the conditions of the Chinese… …   Wikipedia


Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”

We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.