modular exponential Algorithm
The modular exponential algorithm, also known as “modular exponentiation” or "fast exponentiation," is a fundamental algorithm in computer science and cryptography. It is used to compute the remainder of a number raised to a certain power, modulo another number (A^B mod C). This algorithm is particularly useful in public key cryptography, such as the RSA cryptosystem, as it allows for efficient computations of large numbers, which are commonly used to ensure the security of encrypted messages. The basic idea behind modular exponentiation is to break down the exponentiation process into smaller, manageable steps, and then combine these steps using modular arithmetic, resulting in a much faster and efficient calculation.
There are several techniques to implement the modular exponential algorithm, with the most popular being the binary exponentiation, also known as the square-and-multiply method. This technique involves representing the exponent in binary form and then iteratively squaring the base for each bit of the exponent. If the corresponding binary bit is 1, the base is also multiplied by itself. At each step, the intermediate results are reduced modulo the given modulus, which keeps the numbers small and manageable. This method can significantly reduce the number of multiplications required to compute the result, making it much more efficient than the naïve approach of performing exponentiation and then taking the modulus. Other techniques, such as the Montgomery reduction or sliding window method, can further optimize the calculation for specific scenarios or hardware implementations.
"""
Modular Exponential.
Modular exponentiation is a type of exponentiation performed over a modulus.
For more explanation, please check https://en.wikipedia.org/wiki/Modular_exponentiation
"""
"""Calculate Modular Exponential."""
def modular_exponential(base: int, power: int, mod: int):
"""
>>> modular_exponential(5, 0, 10)
1
>>> modular_exponential(2, 8, 7)
4
>>> modular_exponential(3, -2, 9)
-1
"""
if power < 0:
return -1
base %= mod
result = 1
while power > 0:
if power & 1:
result = (result * base) % mod
power = power >> 1
base = (base * base) % mod
return result
def main():
"""Call Modular Exponential Function."""
print(modular_exponential(3, 200, 13))
if __name__ == "__main__":
import doctest
doctest.testmod()
main()
