Order

Definition (Order Modulo $n$)

If $\gcd (a,n)=1$, the order of $a$ modulo $n$, denoted ${\mathrm{ord}}_n(a)$, is the smallest positive integer $r$ such that

$$a^r\equiv 1(\mathrm{mod}n)$$

By Euler’s theorem, such an $r$ exists whenever $\gcd (a,n)=1$.

Theorem

If $r={\mathrm{ord}}_n(a)$, then

$$a^k\equiv 1(\mathrm{mod}n)⟺r\mid k$$

In particular, the order divides any exponent that sends $a$ back to $1$ modulo $n$.

Primitive Roots

An integer $g$ is a primitive root modulo $n$ if

$${\mathrm{ord}}_n(g)=\varphi (n)$$

If $p$ is prime and $g$ is a primitive root modulo $p$, then

$$g,g^2,\dots ,g^{p-1}$$

run through all nonzero residue classes modulo $p$.

Discrete Logarithm

Fix a primitive root $g$ modulo a prime $p$. For each nonzero residue class $j(\mathrm{mod}p)$, there is a unique integer $i$ with $1\le i\le p-1$ such that

$$g^i\equiv j(\mathrm{mod}p)$$

This exponent $i$ is the discrete logarithm of $j$ base $g$, written

$${\log }_g(j\mathrm{mod}p)=i$$

Computing discrete logarithms is believed to be hard in general.

Order of a Power

If ${\mathrm{ord}}_n(a)=r$, then

$${\mathrm{ord}}_n(a^d)=\frac{r}{\gcd (d,r)}$$

This is useful in the analysis of Elgamal and Diffie-Hellman.