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 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.[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.
^Rosen 1993, p. 132.
^Schumacher 1996, p. 88.
^Stinson, Douglas R. (1995), Cryptography / Theory and Practice, CRC Press, pp. 124–128, ISBN 0-8493-8521-0
^Trappe & Washington 2006, pp. 164−169.
^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.
and 23 Related for: Modular multiplicative inverse information
In mathematics, particularly in the area of arithmetic, a modularmultiplicativeinverse of an integer a is an integer x such that the product ax is congruent...
mathematics, a multiplicativeinverse or reciprocal for a number x, denoted by 1/x or x−1, is a number which when multiplied by x yields the multiplicative identity...
a modularmultiplicativeinverse of a modulo m. If a ≡ b (mod m) and a−1 exists, then a−1 ≡ b−1 (mod m) (compatibility with multiplicativeinverse, and...
remainder of c = 8. Modular exponentiation can be performed with a negative exponent e by finding the modularmultiplicativeinverse d of b modulo m using...
In modular arithmetic computation, Montgomery modularmultiplication, more commonly referred to as Montgomery multiplication, is a method for performing...
Fermat's little theorem. Inverse: [(−a mod n) + (a mod n)] mod n = 0. b−1 mod n denotes the modularmultiplicativeinverse, which is defined if and only...
logarithm from pn − 1 and exponentiating the result. By making a modularmultiplicativeinverse table for the finite field and doing a lookup. By mapping to...
{\frac {a}{b}}} does not denote the modularmultiplication of a {\displaystyle a} times the modularmultiplicativeinverse of b {\displaystyle b} but rather...
Inversive congruential generators are a type of nonlinear congruential pseudorandom number generator, which use the modularmultiplicativeinverse (if...
every nonzero element a has a unique modularmultiplicativeinverse, a−1 such that aa−1 = a−1a ≡ 1 mod m. This inverse can be found by solving the congruence...
\ 1{\pmod {n}}}. In other words, the multiplicative order of a modulo n is the order of a in the multiplicative group of the units in the ring of the...
subgroup of a multiplicative group of integers modulo n {\displaystyle n} , where n {\displaystyle n} is prime, the modularmultiplicativeinverse can be computed...
the multiplication is associative, commutative, and that the class of 1 is the unique multiplicative identity. Finally, given a, the multiplicative inverse...
{\displaystyle D(x)=a^{-1}(x-b){\bmod {m}}} where a−1 is the modularmultiplicativeinverse of a modulo m. I.e., it satisfies the equation 1 = a a − 1 mod...
{\displaystyle \gcd(R,m)=1,} let R − 1 {\displaystyle R^{-1}} be the modularmultiplicativeinverse of R {\displaystyle R} (i.e., 0 < R − 1 < m {\displaystyle 0<R^{-1}<m}...
is a positive fraction with one as its numerator, 1/n. It is the multiplicativeinverse (reciprocal) of the denominator of the fraction, which must be a...
2j ≡ 1 (mod 3) The Euclidean modularmultiplicativeinverse of 2 mod 3 is 2. After multiplying both sides with the inverse, we obtain: j ≡ 2 × 1 (mod 3)...
48\div 8=48\times {\tfrac {1}{8}}} . The multiplicative identity element is 1 and the multiplicativeinverse of a number is the reciprocal of that number...
the others: the key itself for the first half of the cipher, its multiplicativeinverse mod n for the last half, and the XOR of these two for the middle...
applying the group operation to g or its inverse. Each element can be written as an integer power of g in multiplicative notation, or as an integer multiple...
Global Information
