Modular multiplicative inverse

In mathematics, particularly in the area of arithmetic, a modular multiplicative inverse of an integer $a$ is an integer $x$ such that the product $ax$ is congruent to 1 with respect to the modulus $m$ .^[1] In the standard notation of modular arithmetic this congruence is written as

which is the shorthand way of writing the statement that $m$ divides (evenly) the quantity $ax - 1$ , or, put another way, the remainder after dividing $ax$ by the integer $m$ is 1. If $a$ does have an inverse modulo $m$ , then there are an infinite number of solutions of this congruence, which form a congruence class with respect to this modulus. Furthermore, any integer that is congruent to $a$ (i.e., in $a$ 's congruence class) has any element of $x$ 's congruence class as a modular multiplicative inverse. Using the notation of ${\overline {w}}$ to indicate the congruence class containing $w$ , this can be expressed by saying that the modulo multiplicative inverse of the congruence class ${\overline {a}}$ is the congruence class ${\overline {x}}$ such that:

where the symbol $\cdot _{m}$ denotes the multiplication of equivalence classes modulo $m$ .^[2] Written in this way, the analogy with the usual concept of a multiplicative inverse in the set of rational or real numbers is clearly represented, replacing the numbers by congruence classes and altering the binary operation appropriately.

As with the analogous operation on the real numbers, a fundamental use of this operation is in solving, when possible, linear congruences of the form

Finding modular multiplicative inverses also has practical applications in the field of cryptography, e.g. public-key cryptography and the RSA algorithm.^[3]^[4]^[5] A benefit for the computer implementation of these applications is that there exists a very fast algorithm (the extended Euclidean algorithm) that can be used for the calculation of modular multiplicative inverses.

The value $\phi (m)$ must be known and the most efficient known computation requires $m$ 's . Factorization is widely believed to be a computationally hard problem. However, calculating $\phi (m)$ is straightforward when the prime factorization of $m$ is known.

factorization

The relative cost of exponentiation. Though it can be implemented more efficiently using , when large values of $m$ are involved this is most efficiently computed with the Montgomery reduction method, that method, itself, requiring a modular inverse mod $m$ , which is what was to be calculated in the first place. Without the Montgomery method, the standard binary exponentiation, which requires division mod $m$ at every step, is a slow operation when $m$ is large.

modular exponentiation

– a pseudo-random number generator that uses modular multiplicative inverses

Inversive congruential generator

Rational reconstruction (mathematics)

Ireland, Kenneth; Rosen, Michael (1990), A Classical Introduction to Modern Number Theory (2nd ed.), Springer-Verlag, 0-387-97329-X

ISBN

Rosen, Kenneth H. (1993), Elementary Number Theory and its Applications (3rd ed.), Addison-Wesley, 978-0-201-57889-8

ISBN

(1996). Chapter Zero: Fundamental Notions of Abstract Mathematics. Addison-Wesley. ISBN 0-201-82653-4.

Schumacher, Carol

Trappe, Wade; Washington, Lawrence C. (2006), Introduction to Cryptography with Coding Theory (2nd ed.), Prentice-Hall, 978-0-13-186239-5

ISBN

"Modular Inverse". MathWorld.

Weisstein, Eric W.

provides a solved example of solving the modulo multiplicative inverse using Euclid's Algorithm

Modular multiplicative inverse

factorization

modular exponentiation

Inversive congruential generator

Rational reconstruction (mathematics)

ISBN

ISBN

Schumacher, Carol

ISBN

Weisstein, Eric W.

Guevara Vasquez, Fernando