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 c 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 = be mod m. From the definition of division, it follows that 0 ≤ c < m. For example, given b = 5, e = 3 and m = 13, dividing 53 = 125 by 13 leaves a remainder of c = 8. When b and m are relatively prime, one can also allow the exponent e to be negative by finding the multiplicative inverse d of b modulo m (for instance by using extended Euclidean algorithm). More precisely:
c = be 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.
Direct method The most direct method of calculating a modular exponent is to calculate be directly, then to take this number modulo m. Consider trying to compute c, given b = 4, e = 13, and m = 497:
c ≡ 413 (mod 497) One could use a calculator to compute 413; this comes out to 67,108,864. Taking this value modulo 497, the answer c is determined to be 445. Note that b is only one digit in length and that e is only two digits in length, but the value be is eight digits in length. In strong cryptography, b is often at least 1024 bits. Consider b = 5 × 1076 and e = 17, both of which are perfectly reasonable values. In this example, b is 77 digits in length and e is two digits in length, but the value be is 1,304 decimal digits in length. Such calculations are possible on modern computers, but the sheer magnitude of such numbers causes the speed of calculations to drop considerably. As b and e increase even further to provide better security, the value be becomes unwieldy. The time required to perform the exponentiation depends on the operating environment and the processor. The method described above requires Θ(e) multiplications to complete.
Memory-efficient method Keeping the numbers smaller requires additional modular reduction operations, but the reduced size makes each operation faster, saving time (as well as memory) overall. This algorithm makes use of the identity
(a ⋅ b) mod m = [(a mod m) ⋅ (b mod m)] mod m The modified algorithm is:
Inputs An integer b (base), integer e (exponent), and a positive integer m (modulus) Outputs The modular exponent c where c = be mod m Initialise c = 1 and loop variable e′ = 0 While e′ < e do Increment e′ by 1 Calculate c = (b ⋅ c) mod m Output c Note that at the end of every iteration through the loop, the equation c ≡ be′ (mod m) holds true. The algorithm ends when the loop has been executed e times. At that point c contains the result of be mod m. In summary, this algorithm increases e′ by one until it is equal to e. At every step multiplying the result from the previous iteration, c, by b and performing a modulo operation on the resulting product, thereby keeping the resulting c a small integer. The example b = 4, e = 13, and m = 497 is presented again. The algorithm performs the iteration thirteen times:
(e′ = 1) c = (4 ⋅ 1) mod 497 = 4 mod 497 = 4 (e′ = 2) c = (4 ⋅ 4) mod 497 = 16 mod 497 = 16 (e′ = 3) c = (4 ⋅ 16) mod 497 = 64 mod 497 = 64 (e′ = 4) c = (4 ⋅ 64) mod 497 = 256 mod 497 = 256 (e′ = 5) c = (4 ⋅ 256) mod 497 = 1024 mod 497 = 30 (e′ = 6) c = (4 ⋅ 30) mod 497 = 120 mod 497 = 120 (e′ = 7) c = (4 ⋅ 120) mod 497 = 480 mod 497 = 480 (e′ = 8) c = (4 ⋅ 480) mod 497 = 1920 mod 497 = 429 (e′ = 9) c = (4 ⋅ 429) mod 497 = 1716 mod 497 = 225 (e′ = 10) c = (4 ⋅ 225) mod 497 = 900 mod 497 = 403 (e′ = 11) c = (4 ⋅ 403) mod 497 = 1612 mod 497 = 121 (e′ = 12) c = (4 ⋅ 121) mod 497 = 484 mod 497 = 484 (e′ = 13) c = (4 ⋅ 484) mod 497 = 1936 mod 497 = 445 The final answer for c is therefore 445, as in the direct method. Like the first method, this requires O(e) multiplications to complete. However, since the numbers used in these calculations are much smaller than the numbers used in the first algorithm's calculations, the computation time decreases by a factor of at least O(e) in this method. In pseudocode, this method can be performed the following way:
function modular_pow(base, exponent, modulus) is if modulus = 1 then return 0 c := 1 for e_prime = 0 to exponent-1 do c := (c * base) mod modulus return c
Right-to-left binary method A third method drastically reduces the number of operations to perform modular exponentiation, while keeping the same memory footprint as in the previous method. It is a combination of the previous method and a more general principle called exponentiation by squaring (also known as binary exponentiation). First, it is required that the exponent e be converted to binary notation. That is, e can be written as:
e = ∑ i = 0 n − 1 a i 2 i {\displaystyle e=\sum _{i=0}^{n-1}a_{i}2^{i}}
In such notation, the length of e is n bits. ai can take the value 0 or 1 for any i such that 0 ≤ i < n. By definition, an − 1 = 1. The value be can then be written as:
… excerpt ends here. Continue reading the full article.
