## Cryptography

Diffie-Hellman key exchange works by agreeing on two publicly shared values: a large prime number $q$ and a primitive root $g$. Alice and Bob each generate a secret key---a large random number---$x_a$ and $x_b$ respectively, and each raise the primitive root to the power of the secret key, modulo the large prime number.

The results are sent to each other and the shared key is computed by raising the received value to the secret key modulo the primitive root.

Given a prime number $q$, a primitive root $g$ is a number such that every number from 1 up to $q - 1$ can be computed by raising the primitive root to some number $k$.

A common analogy is that of mixing paint.

May 4, 2016