THE ONE-WAY FUNCTION easy forward, hard back — the asymmetry all of cryptography stands on
A one-way function is cheap to compute and (believed) expensive to invert. Multiplying two primes is instant; factoring the product is not. Raising g to a power mod p is a handful of squarings; recovering the exponent — the discrete logarithm — means searching. That gap between forward and backward is the entire foundation of modern cryptography: public keys, signatures, key exchange, commitments all rest on a door that swings one way. No one has proven such functions exist (it would settle P vs NP), but several are trusted because decades of attack have not cracked them.
THE TECHNIQUE forward O(log): g^x mod p; inverse: search for x (discrete log)
The demo computes y = 5^9 mod 23 in a few squarings (forward, cheap), then recovers the exponent 9 by scanning — the inverse has no shortcut here: live demo
HISTORY & CREDIT Needham ~1967 · Diffie-Hellman 1976
“If you can compute it, you can undo it.” — not if inverting means factoring or a discrete log; the door swings one way. cited
forward · y = g^x mod p — O(log x) by square-and-multiply (dart 410). backward · find x from y — the discrete log; no efficient algorithm known. origin & stakes · used for password storage by Roger Needham (~1967; Wilkes, 1968), formalized for public-key crypto by Diffie-Hellman (1976); a proof one-way functions exist would resolve P ≠ NP.
A function trivial to walk forward and (believed) infeasible to walk back — the asymmetry every public key is built on. asymmetry
RECOMMEND FOR I-13 forward cheap, inverse searched, on the compiler
On the canonical compiler, y=5^9 mod 23 = 11 costs a few squarings; recovering x=9 required scanning candidates:
$ i13 run zd_onewayfn.i13 # forward modexp vs discrete-log search
RUN OK · 1209 step(s) · peak stack 6 · call depth 15
y = 11 -- 5^9 mod 23, cheap forward
recovered = 9 -- found only by scanning x = 0..p
asymmetry = 1
Recommend as a NULL — a complexity asymmetry, not an output invariant. One-wayness is a statement about the cost of inverting (B40 resource) and about what an adversary cannot feasibly do (B41 recognizer/hardness); its very existence is a theorem-level open question (B39, P vs NP). None of that is extra structure two same-function mechanisms carry differently — it is a property of the function’s inverse. i13 grounds the gap (cheap forward, searched inverse). NULL — the bedrock, but not an axis.