← All Labs
INTERACTIVE APPLET · NUMBER THEORY & CRYPTOGRAPHY

Modular Arithmetic as a Clock & the Discrete-Log Trap

A clock only knows the numbers 0…11: add 5 hours to 9 o'clock and you land on 2, not 14. Do all your arithmetic that way — "mod N" — and multiplication starts drawing pictures. Wrap the numbers 0…N−1 around a circle and join every point i to k·i mod N: out fall cardioids, nephroids and rose windows, the same envelopes you see in a coffee cup. Then swap multiplication for repeated multiplication — powers gˣ mod p — and the tidy pattern shatters into a wild hop around the ring. Going forward is one multiply. Going backward, recovering the secret exponent x, is so hard it guards your bank login. Two knobs, one deep idea.

everything is computed mod N

Multiplication mod N, drawn as chords on a circle

Slide the multiplier and the modulus · watch the envelope morph
Canvas · exact integer arithmetic

DRIVE IT

ENVELOPE
k = 2 makes a cardioid

MULTIPLIER k

MODULUS N (points)

WALKTHROUGH

    AHA

    RESEARCH NOTE

    Why the pictures? On the times-table circle, point \(i\) sits at angle \(2\pi i/N\) and connects to \(k\,i \bmod N\). The chord family has an envelope — a caustic — and for integer \(k\) it is an epicycloid with \(k-1\) cusps: \(k=2\) gives the one-cusped cardioid, \(k=3\) the two-cusped nephroid, and so on. It is the very same light caustic that pools at the bottom of a coffee mug.

    Why the trap? Fix a prime \(p\) and a primitive root \(g\) (a base whose powers hit every nonzero residue). The map \(x \mapsto g^{x}\bmod p\) is easy to run forward — square-and-multiply needs only \(\sim\log x\) steps. But inverting it, the discrete logarithm \(x=\log_g y \pmod p\), has no known fast method for general \(p\); the best classical attacks run in sub-exponential, not polynomial, time. That asymmetry — trivial one way, intractable the other — is a one-way function, and it is exactly what Diffie–Hellman key exchange and the ElGamaI/DSA family are built on. Read more: the Mathologer "Times Tables, Mandelbrot" video for the envelopes; Diffie & Hellman (1976); and any intro-crypto text on the discrete-log assumption.