binary exp mod Algorithm
The binary exponentiation modulo algorithm, or binary exp mod algorithm, is a highly efficient technique for computing large powers of a number modulo some integer. It is a widely used algorithm in computer science, cryptography, and number theory, where large-scale modular arithmetic is often required. This algorithm is based on the fundamental principle of modular exponentiation, which states that (a^b) mod m = (a^(b/2) mod m)^2 mod m, if b is even, and (a^b) mod m = (a * (a^(b-1) mod m)) mod m, if b is odd. The binary exp mod algorithm uses this principle to perform repeated squaring and multiplication operations, reducing the number of total calculations required and thus, speeding up the computation process.
To implement the binary exp mod algorithm, we start by representing the exponent as a binary number, as this enables the algorithm to take advantage of the binary representation's inherent properties. For each bit in the binary representation of the exponent, starting from the most significant bit, we perform a squaring operation, followed by a multiplication operation if the bit is 1. Throughout this process, we continuously apply the modulo operator to keep the intermediate results from growing too large. This iterative approach allows the algorithm to compute the desired result in logarithmic time complexity, making it highly efficient and well-suited for handling large numbers. As a result, the binary exp mod algorithm is widely adopted in various applications, such as the implementation of cryptographic protocols like the RSA cryptosystem, the Diffie-Hellman key exchange, and the ElGamal encryption scheme.
def bin_exp_mod(a, n, b):
"""
>>> bin_exp_mod(3, 4, 5)
1
>>> bin_exp_mod(7, 13, 10)
7
"""
# mod b
assert not (b == 0), "This cannot accept modulo that is == 0"
if n == 0:
return 1
if n % 2 == 1:
return (bin_exp_mod(a, n - 1, b) * a) % b
r = bin_exp_mod(a, n / 2, b)
return (r * r) % b
if __name__ == "__main__":
try:
BASE = int(input("Enter Base : ").strip())
POWER = int(input("Enter Power : ").strip())
MODULO = int(input("Enter Modulo : ").strip())
except ValueError:
print("Invalid literal for integer")
print(bin_exp_mod(BASE, POWER, MODULO))
