Modular exponentiation

This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed. Find sources: "Modular exponentiation" – news · newspapers · books · scholar · JSTOR (February 2018) (Learn how and when to remove this message)

Modular exponentiation is exponentiation performed over a modulus. It is useful in computer science, especially in the field of public-key cryptography, where it is used in both Diffie–Hellman key exchange and RSA public/private keys.

Modular exponentiation is the remainder when an integer b (the base) is raised to the power e (the exponent), and divided by a positive integer m (the modulus); that is, c = b^e mod m. From the definition of division, it follows that 0 ≤ c < m.

For example, given b = 5, e = 3 and m = 13, dividing 5³ = 125 by 13 leaves a remainder of c = 8.

Modular exponentiation can be performed with a negative exponent e by finding the modular multiplicative inverse d of b modulo m using the extended Euclidean algorithm. That is:

c = b^e mod m = d^−e mod m, where e < 0 and b ⋅ d ≡ 1 (mod m).

Modular exponentiation is efficient to compute, even for very large integers. On the other hand, computing the modular discrete logarithm – that is, finding the exponent e when given b, c, and m – is believed to be difficult. This one-way function behavior makes modular exponentiation a candidate for use in cryptographic algorithms.