Modular multiplicative inverse

From Wikipedia, the free encyclopedia
Jump to: navigation, search

The modulo multiplicative inverse for the congruence class is the congruence class such that:

, where , , and are congruence classes with respect to the modulus number m.[1]

This concept is analogous to the concept of the multiplicative inverse over the set of rational numbers. The only difference between the analogous concept and the one discussed here is the binary operator and the sets to which the operator is applied to. For example, note that is used instead of .

There are many applications in the field of cryptography, particularly in public-key cryptography and the RSA algorithm, which use modular arithmetic extensively. Part of the appeal in application areas is the existence of a very fast algorithm (the extended Euclidean algorithm) that can be used to calculate these modular inverses. This is a fundamental operation in the multiplicative group of integers modulo n and so, is critical in the study of number theory.

Definitions, existence, uniqueness, and well-defined solutions[edit]

Multiplication modulo m is defined as:

.[1]

The modulo multiplicative inverse for any exists if and only if and m are coprime (i.e., if gcd(a, m) = 1).[2]

It is established by theorem that this solution will be unique.[1] 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. Note, however, that the members of will vary depending on the restrictions placed on , such as limiting membership to . In the latter case, the set would be defined as: where i is an index number over the number of members in the congruence class and starts at 1.

Modulo division is the inverse operation to modulo multiplication. There are cases where modulo division m is not well-defined.[1] 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.[1] Modulo division is well-defined in , where p represents the prime numbers.

Example[edit]

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.[3] 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.[4][5] 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.

Computation[edit]

Extended Euclidean algorithm[edit]

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 and 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

by the definition of congruence, m | ax − 1, which means that m is a divisor of ax − 1. This, in turn, 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, 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[edit]

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

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:

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.

Applications[edit]

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:

  1. 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.
  2. 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.

See also[edit]

Notes[edit]

  1. ^ a b c d e Schumacher, Carol (2001). Chapter Zero: Fundamental Notions of Abstract Mathematics. ISBN 0-201-43724-4. 
  2. ^ Shoup, Victor (2005), A Computational Introduction to Number Theory and Algebra, Cambridge University Press, Theorem 2.4, p. 15, ISBN 9780521851541 .
  3. ^ Rosen 1993, p. 132
  4. ^ Ireland & Rosen 1990, p. 29
  5. ^ Other notations are often used, including [a] and [a]n.
  6. ^ Thomas Koshy. Elementary number theory with applications, 2nd edition. ISBN 978-0-12-372487-8. P. 346.

References[edit]

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

External links[edit]