modular exponentiation is a type of exponentiation performed over a modulus. it is particularly useful in computer science, especially in the field of public-key cryptography. a "modular exponentiation" calculates the remainder when a positive integer b (the base) raised to the e-th power (the exponent), b^e , is divided by a positive integer m, called the modulus. in symbols, given base b, exponent e, and modulus m, the modular exponentiation c is: c \equiv b^e \pmod{m} for example, given b = 5, e = 3, and m = 13, the solution, c = 8, is the remainder of dividing 5^3 by 13. if b, e, and m are non-negative, and b < m, then a unique solution c exists with the property 0 â¤ c &lt; m. 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 \equiv b^{e} \equiv d^{\left|e\right|} \pmod{m} where e < 0 and b \cdot d \equiv 1 \pmod{m} modular exponentiation problems similar to the one described above are considered easy to solve, even when the numbers involved are enormous. on the other hand, computing the discrete logarithm - that is, the task of finding the exponent e if 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. ==straightforward method== the most straightforward method of calculating a modular exponent is to calculate b'e directly, then to take this number modulo m. consider trying to compute c, given b = 4, e = 13, and m = 497: : c \equiv 4^{13} \pmod{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 b'e is 8 digits in length. in strong cryptography, b is often at least 256 binary digits (77 decimal digits). consider b = 5 &times; 1076 and e = 17, both of which are perfectly reasonable values. in this example, b is 77 digits in length and e is 2 digits in length, but the value b'e 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 slow considerably. as b and e increase even further to provide better security, the value b'e becomes unwieldy. the time required to perform the exponentiation depends on the operating environment and the processor. the method described above requires o(e) multiplications to complete. ==memory-efficient method== a second method to compute modular exponentiation requires more operations than the
Cryptographic_algorithms Modular_arithmetic Number_theoretic_algorithms