Modular multiplicative inverse
In mathematics, in particular, the area of number theory, 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. 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 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) will have any element of x's congruence class as a modular multiplicative inverse. Using the notation of w to indicate the congruence class containing w, this can be expressed by saying that the modulo multiplicative inverse of the congruence class is the congruence class such that:
where the symbol denotes the multiplication of equivalence classes modulo m. 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, i.e. public-key cryptography and the RSA Algorithm. In mathematical theory, assumptions about the properties of binary operators (for example the associative property and the commutative property) are often used as axioms in fields of study such as number theory and also two sub-disciplines of abstract algebra, group theory and ring theory.
Definitions, existence, uniqueness, and well-defined solutions
Multiplication modulo m is defined as:
It is established by theorem that this solution will be unique. Representing the multiplicative inverse as , for and if there exists an x that satisfies the equation then the solution to this equation will be unique: , which implies that the solution to will be unique. Modulo division is the inverse operation to modulo multiplication. There are cases where modulo division m is not well-defined. In this context, well-defined means application of the binary operator over the applicable sets is sufficiently well described so as to yield a single unambiguous result. Modulo division is well-defined in , where p represents the prime numbers.
Consider the modular multiplicative inverse of 3 modulo 11, call it x. In order for x to exist it must be that 3 and 11 are coprime, which is true. Notationally,
This is equivalent to the computation of finding x such that
By observation (systematic techniques are given below), the one positive value of x that satisfies this congruence and is less than 11 is 4 since
and no other such values of x satisfy this congruence. However, other integers, not under these restrictions, such as −7, 15, and 26 also satisfy this congruence. In fact, the set is the set of all integers that satisfy the congruence, that is, the set of all multiplicative inverses of 3 modulo 11. An equivalence class of integers modulo n may be represented by any of its members. The equivalence class modulo n containing the integer a is often denoted by and the modulus n may be omitted if it is clear from the context. Thus, the multiplicative inverse of 3 modulo 11 could be denoted by or just . Some authors systematically choose the smallest non-negative member of an equivalence class to be its representative and may not use a special notation for the equivalence class of that representative.
Extended Euclidean algorithm
|The Wikibook Algorithm Implementation has a page on the topic of: Extended Euclidean algorithm|
where a and 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, which means that m is a divisor of ax − 1. This, in turn, means that
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, a needs to be coprime to the modulus, or the inverse won't exist.
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:
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:
In the special case when m is a prime, φ(m) = m − 1 and the modular inverse is given by
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 value φ(m) must be known, whose most efficient computation requires m's factorization. Factorization is widely believed to be a computationally hard problem. However, calculating φ(m) is straightforward when the prime factorisation of m is known.
- The relative cost of 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 was to be calculated 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.
The modular multiplicative inverse has many applications in algorithms, particularly those related to number theory, since many such algorithms rely heavily on the theory of modular arithmetic. As a simple example, consider the exact division problem where you have a list of odd word-sized numbers each divisible by k and you wish to divide them all by k. One solution is as follows:
- Use the extended Euclidean algorithm to compute k−1, the modular multiplicative inverse of k mod 2w, where w is the number of bits in a word. This inverse will exist since the numbers are odd and the modulus has no odd factors.
- For each number in the list, multiply it by k−1 and take the least significant word of the result.
On many machines, particularly those without hardware support for division, division is a slower operation than multiplication, so this approach can yield a considerable speedup. The first step is relatively slow but only needs to be done once.
- Equivalence Relation
- Congruence relation
- Modular arithmetic
- Multiplicative group of integers modulo n
- Inversive congruential generator
- Number theory
- Ring (mathematics)
- Group theory
- Rational reconstruction (mathematics)
- Rosen 1993, p. 132
- Schumacher, Carol (2001). Chapter Zero: Fundamental Notions of Abstract Mathematics. ISBN 0-201-43724-4.
- Stinson, Douglas R. (1995), Cryptography / Theory and Practice, CRC Press, pp. 124–128, ISBN 0-8493-8521-0
- Trappe, Wade; Washington, Lawrence C. (2006), Introduction to Cryptography with Coding Theory (2nd ed.), Prentice-Hall, pp. 164–169, ISBN 978-0-13-186239-5
- Moriarty, K.; Kaliski, B.; Jonsson, J.; Rusch, A. (2016). "PKCS #1: RSA Cryptography Specifications Version 2.2". Internet Engineering Task Force RFC 8017. Internet Engineering Task Force. Retrieved January 21, 2017.
- Shoup, Victor (2005), A Computational Introduction to Number Theory and Algebra, Cambridge University Press, Theorem 2.4, p. 15, ISBN 9780521851541.
- Ireland & Rosen 1990, p. 29
- Other notations are often used, including [a] and [a]n.
- Thomas Koshy. Elementary number theory with applications, 2nd edition. ISBN 978-0-12-372487-8. P. 346.
- Ireland, Kenneth; Rosen, Michael (1990), A Classical Introduction to Modern Number Theory (2nd ed.), Springer-Verlag, ISBN 0-387-97329-X
- Rosen, Kenneth H. (1993), Elementary Number Theory and its Applications (3rd ed.), Addison-Wesley, ISBN 978-0-201-57889-8
- Schumacher, Carol (1996). Chapter Zero: Fundamental Notions of Abstract Mathematics. Addison-Wesley. ISBN 0-201-82653-4.