POW WITH MODULAR ARITHMETIC

#!/usr/bin/env python3
"""
POW WITH MODULAR ARITHMETIC
Use three-argument pow() for cryptography and large numbers
"""

print("=== Modular Exponentiation (crypto basics) ===")
base = 7
exponent = 3
modulus = 5

# pow(base, exp, mod) is much faster than (base ** exp) % mod
result = pow(base, exponent, modulus)
print(f"{base}^{exponent} mod {modulus} = {result}")

print("\n=== RSA-style Calculation ===")
# Simplified RSA example
message = 42
public_key = (17, 3233)  # (e, n)
e, n = public_key

encrypted = pow(message, e, n)
print(f"Original message: {message}")
print(f"Encrypted: {encrypted}")

# Decrypt (using private key)
private_key = (2753, 3233)  # (d, n)
d, n = private_key
decrypted = pow(encrypted, d, n)
print(f"Decrypted: {decrypted}")

print("\n=== Check Last Digit of Large Power ===")
# Find last digit of 2^1000
last_digit = pow(2, 1000, 10)
print(f"Last digit of 2^1000 is: {last_digit}")

print("\n=== Fermat's Little Theorem Check ===")
p = 7  # prime number
a = 3
# a^(p-1) mod p should equal 1 for prime p
result = pow(a, p-1, p)
print(f"{a}^{p-1} mod {p} = {result}")
print(f"{'Prime!' if result == 1 else 'Not prime or wrong calculation'}")