Timewise — Haskell Modular Exponentiation

The Functions

n = 0x10000000000000000000000000000000055

a x 0 = x
a x c = a (x + 1 - (x + 1) `div` n * n) (c - 1)

m x 0 = 0
m x 1 = x
m x c = a x (m x (c - 1))

e x 0 = 1
e x 1 = x
e x c = m x (e x (c - 1))

main = print $ e secret 31337

Function a(x,c) simplifies to modular addition: (x + c) mod n. Function m(x,c) implements modular multiplication: (x * c) mod n. Function e(x,c) implements modular exponentiation: x^c mod n.

The Problem

We need: secret^31337 ≡ 35979253760252124533044326983738660434153 (mod n)

Where n = 87112285931760246646623899502532662132821 (confirmed prime).

Solution: Fermat's Little Theorem

For prime n and gcd(secret, n) = 1: secret ≡ target^d (mod n), where d is the modular multiplicative inverse of 31337 modulo (n-1).

n = 0x10000000000000000000000000000000055
target = 35979253760252124533044326983738660434153
exponent = 31337

d = mod_inverse(exponent, n - 1)
secret = pow(target, d, n)
# secret = 3133333333333333333337

# Verify
assert pow(secret, exponent, n) == target

Answer