SEMI-ADVANCED POW() EXAMPLES

#!/usr/bin/env python3
"""
SEMI-ADVANCED POW() EXAMPLES
Modular arithmetic, optimization, and advanced applications
"""

import time

print("=" * 60)
print("SEMI-ADVANCED POW() - Modular Arithmetic & Optimization")
print("=" * 60)

# Example 1: Three-argument form (modular exponentiation)
print("\n1. Modular Exponentiation: pow(base, exp, mod)")
print("-" * 40)
print("Calculate (base^exp) % mod efficiently:\n")

base, exp, mod = 7, 100, 13
result_modular = pow(base, exp, mod)
print(f"pow({base}, {exp}, {mod}) = {result_modular}")
print(f"This computes ({base}^{exp}) mod {mod} efficiently")

print("\nComparison with manual modulo:")
result_manual = pow(base, exp) % mod
print(f"pow({base}, {exp}) % {mod} = {result_manual}")
print(f"Both methods give same result: {result_modular == result_manual}")

# Example 2: Why modular pow is more efficient
print("\n2. Efficiency: Modular vs Manual (Large Numbers)")
print("-" * 40)

base, exp, mod = 12345, 67890, 10007

# Using three-argument pow (efficient)
start = time.time()
result_efficient = pow(base, exp, mod)
time_efficient = time.time() - start

# Using manual method (creates huge intermediate number)
start = time.time()
result_manual = pow(base, exp) % mod
time_manual = time.time() - start

print(f"Base: {base}, Exponent: {exp}, Modulo: {mod}\n")
print(f"Three-argument pow(): {result_efficient}")
print(f"  Time: {time_efficient:.6f} seconds")
print(f"\nManual (pow then mod): {result_manual}")
print(f"  Time: {time_manual:.6f} seconds")
print(f"\nSpeedup: {time_manual / time_efficient:.2f}x faster" if time_efficient > 0 else "")

# Example 3: Checking last digits (modulo 10, 100, 1000)
print("\n3. Finding Last Digits of Large Powers")
print("-" * 40)

base = 7
exp = 1000

last_1_digit = pow(base, exp, 10)
last_2_digits = pow(base, exp, 100)
last_3_digits = pow(base, exp, 1000)

print(f"Calculating {base}^{exp}:")
print(f"  Last 1 digit: {last_1_digit}")
print(f"  Last 2 digits: {last_2_digits:02d}")
print(f"  Last 3 digits: {last_3_digits:03d}")

# Example 4: Modular patterns (cyclic behavior)
print("\n4. Modular Patterns: Powers Cycle")
print("-" * 40)

base = 3
mod = 7

print(f"Pattern of {base}^n mod {mod}:")
print("n  | 3^n mod 7")
print("---|----------")

for n in range(1, 13):
    result = pow(base, n, mod)
    print(f"{n:2d} | {result}")

print("\nNotice the pattern repeats!")

# Example 5: Cryptography basics - modular inverse
print("\n5. Modular Inverse Using pow()")
print("-" * 40)
print("For prime modulus p, modular inverse of a is: pow(a, p-2, p)\n")

a = 38
p = 97  # Prime number

# Calculate modular inverse
inv = pow(a, p - 2, p)
# Verify: (a * inv) mod p should equal 1
verification = (a * inv) % p

print(f"Number: {a}")
print(f"Prime modulus: {p}")
print(f"Modular inverse: {inv}")
print(f"Verification: ({a} * {inv}) mod {p} = {verification}")
print(f"Is inverse correct? {verification == 1}")

# Example 6: RSA-like calculation (simplified)
print("\n6. RSA-Style Encryption/Decryption (Simplified)")
print("-" * 40)

message = 42
e = 17  # Public exponent
d = 2753  # Private exponent (pre-calculated)
n = 3233  # Modulus (61 * 53)

# Encryption: c = m^e mod n
ciphertext = pow(message, e, n)
print(f"Original message: {message}")
print(f"Public key (e, n): ({e}, {n})")
print(f"Encrypted: {ciphertext}")

# Decryption: m = c^d mod n
decrypted = pow(ciphertext, d, n)
print(f"\nPrivate key (d): {d}")
print(f"Decrypted: {decrypted}")
print(f"Decryption successful? {decrypted == message}")

# Example 7: Fermat's Little Theorem verification
print("\n7. Fermat's Little Theorem: a^(p-1) ≡ 1 (mod p)")
print("-" * 40)
print("For prime p and a not divisible by p:\n")

primes = [5, 7, 11, 13, 17]
a = 3

print(f"Testing with a = {a}:")
print("Prime p | a^(p-1) mod p")
print("--------|---------------")

for p in primes:
    result = pow(a, p - 1, p)
    print(f"   {p:2d}   |      {result}")

print("\nAll results are 1, confirming the theorem!")

# Example 8: Finding remainders for large calculations
print("\n8. Calendar Calculations: Day of Week")
print("-" * 40)
# If today is day 0, what day is it after 10^100 days?

days_in_week = 7
huge_days = pow(10, 100)  # Can't compute this directly

# But we can find remainder efficiently
day_of_week = pow(10, 100, days_in_week)

weekdays = ["Sunday", "Monday", "Tuesday", "Wednesday",
            "Thursday", "Friday", "Saturday"]

print(f"If today is {weekdays[0]},")
print(f"what day is it after 10^100 days?")
print(f"\nRemainder when dividing by 7: {day_of_week}")
print(f"Answer: {weekdays[day_of_week]}")

# Example 9: Chinese Remainder Theorem application
print("\n9. Solving System with Modular Arithmetic")
print("-" * 40)
# Find x such that x ≡ 2 (mod 5) and x ≡ 3 (mod 7)

# Testing possible values
print("Finding x where x ≡ 2 (mod 5) and x ≡ 3 (mod 7):\n")

solutions = []
for x in range(0, 100):
    if pow(x, 1, 5) == 2 and pow(x, 1, 7) == 3:  # x mod 5 == 2 and x mod 7 == 3
        solutions.append(x)
        if len(solutions) <= 5:
            print(f"  x = {x}")

print(f"\nPattern: solutions differ by {5 * 7} = 35")
print(f"General solution: x = {solutions[0]} + 35k (k = 0, 1, 2, ...)")

# Example 10: Performance with very large numbers
print("\n10. Handling Astronomical Numbers")
print("-" * 40)

# Calculate something that would overflow without modular arithmetic
base = 123456789
exp = 987654321
mod = 1000000007  # Large prime often used in competitive programming

print(f"Computing {base}^{exp} mod {mod}")
print("(Direct computation would create number with ~80 million digits!)\n")

start = time.time()
result = pow(base, exp, mod)
elapsed = time.time() - start

print(f"Result: {result}")
print(f"Computed in: {elapsed:.6f} seconds")
print(f"\nWithout modular form, this would:")
print(f"  - Require gigabytes of memory")
print(f"  - Take hours or days to compute")

# Example 11: Digital signatures verification
print("\n11. Digital Signature Verification Concept")
print("-" * 40)

# Simplified signature scheme
message_hash = 1234
private_key = 107
public_key = 29
modulus = 187

# Sign: signature = hash^private_key mod n
signature = pow(message_hash, private_key, modulus)
print(f"Message hash: {message_hash}")
print(f"Signature: {signature}")

# Verify: hash should equal signature^public_key mod n
verified_hash = pow(signature, public_key, modulus)
print(f"\nVerification:")
print(f"  signature^public_key mod n = {verified_hash}")
print(f"  Original hash = {message_hash}")
print(f"  Valid signature? {verified_hash == message_hash}")

# Example 12: Optimization comparison
print("\n12. Memory Comparison: Huge vs Modular")
print("-" * 40)

base, exp = 999, 10000

# Show size difference
huge_number = pow(base, exp)
modular_result = pow(base, exp, 1000000)

huge_digits = len(str(huge_number))
huge_bytes = huge_number.bit_length() // 8

print(f"Computing {base}^{exp}:")
print(f"\nDirect computation:")
print(f"  Number of digits: {huge_digits:,}")
print(f"  Approximate bytes: {huge_bytes:,}")
print(f"  First 50 digits: {str(huge_number)[:50]}...")
print(f"\nModular computation (mod 1000000):")
print(f"  Result: {modular_result}")
print(f"  Memory: just a few bytes")

print("\n" + "=" * 60)
print("Key Concepts:")
print("  - pow(base, exp, mod) is MUCH faster than pow(base, exp) % mod")
print("  - Essential for cryptography (RSA, signatures)")
print("  - Enables working with astronomical numbers")
print("  - Modular inverse: pow(a, p-2, p) when p is prime")
print("  - Pattern detection through modular cycles")
print("=" * 60)