The Order of a Unit

The discrete log problem may be hard, but we do know some facts about the powers of a unit $a \in\mathbb{Z}_n^*$. Firstly, $a^k = 1$ for some $k$: since there are finitely many units, we must have $a^x = a^y$ for some $x \lt y$ eventually, and since $a^{-1}$ exists we find $a^{y-x} = 1$.

Let $a \in\mathbb{Z}_n^*$. The smallest positive integer $x$ for which $a^x = 1 \pmod{n}$ is called the order of $a$. The sequence $a, a^2, ...$ repeats itself as soon as it reaches $a^x = 1$. (since $a^{x+k} = a^k$), and we have $a^k = 1$ precisely when $k$ is a multiple of $x$.

Example: The powers of $3 \pmod{7}$ are $3, 2, 6, 4, 5, 1$ so the order of $3 \pmod {7}$ is $6$.

The following theorems narrow down the possible values for the order of a unit.

Fermat’s Little Theorem

Theorem: Let $p$ be a prime. Then $a^p = a \pmod{p}$ for any $a \in \mathbb{Z}_p$.

This theorem is often equivalently stated as $a^{p-1} = 1$ for nonzero $a$.

Proof: We first show an identity sometimes referred to as the freshman’s dream: for a prime $p$, we have

\[ (x + y)^p = x^p + y^p \pmod {p}. \]

This is immediate the binomial expansion, because $p$ divides every term except for two terms, that is

\[ (x + y)^p = x^p + y^p + p(...) = x^p + y^p \pmod{p} \]

By induction we have

\[ (x_1 +...+ x_n)^p = x_1^p + ... + x_n^p \]

Thus if we write $a = 1 + ... + 1$ (where there are $a$ 1s), we have

\[ a^p = (1 + ... + 1)^p = 1^p + ... + 1^p = 1 + ... + 1 = a.∎ \]

Fermat’s Theorem gives an alternative way to compute inverses. For $a \in \mathbb{Z}_p^*$, $a^{-1}$ can be computed as $a^{p-2}$, since we have $a \cdot a^{p-2} = 1$ by the theorem.

Euler’s Theorem

Theorem: If $a \in \mathbb{Z}_n^*$ then $a^{\phi(n)} = 1 \pmod{n}$.

This reduces to Fermat’s Little Theorem when $n$ is prime.

Proof: Let $m = \phi(n)$, and label the units $u_1,...,u_m$. Consider the sequence $a u_1,...,a u_m$ (we multiply each unit by $a$). If $a u_i = a u_j$, then multiplying by $a^{-1}$ (which exists since $a$ is a unit) shows $u_i = u_j$, hence the members of the sequence are distinct. Furthermore products of units must also be units, hence $a u_1, ..., a u_m$ must be $u_1,...,u_m$ in some order.

Multiplying all the units together gives

\[ a u_1 ... a u_m = u_1 ... u_m.\]

Rearranging yields

\[ a^{\phi(n)} = a^m = (u_1 ... u_m)(u_1 ... u_m)^{-1} = 1 .∎ \]

Similarly Euler’s Theorem also gives an alternative way to compute inverses. For $a \in \mathbb{Z}_n^*$, $a^{-1}$ can be computed as $a^{\phi(n)-1}$. This is efficient as we may use repeated squaring, but Euclid’s algorithm is still faster (why?) and does not require one to compute $\phi(n)$.

These theorems do not tell us the order of a given unit $a\in\mathbb{Z}_n^*$ but they do narrow it down: let $x$ be the order of $a$. If we know $a^y = 1$ by Euclid’s algorithm we can find $m, n$ such that

\[ d = m x + n y \]

where $d = \gcd(x, y)$. Then

\[ a^d = a^{m x + n y} = (a^x)^m (a^y)^n = 1 \]

thus since $d \le x$ we must have $d = x$ (since $x$ is the smallest positive integer for which $a^x = 1$), and hence $x$ must be a divisor of $y$. Thus by Euler’s Theorem, the order of $a$ divides $\phi(n)$.

These statements are in fact trivial corollaries of Lagrange’s Theorem from group theory. Of course Fermat and Euler died long before group theory was discovered.

Multiplication and Order

Let $x$ be the order of $a\in\mathbb{Z}_n^*$, and $y$ be the order of $b\in\mathbb{Z}_n^*$. What is the order of $a b$?

Suppose $(a b)^k= 1$. Raising both sides to $x$ shows

\[ b^{k x} = 1^k b^{k x} = (a^x)^k b^{k x} = (a b)^{k x} = 1 .\]

Since $b$ has order $y$ we see that $y | k x$.

Suppose $x, y$ are coprime. Then we must have $y | k$. Similarly $x | k$, hence $k$ must be a multiple of $x y$. On the other hand, we have $(ab)^{x y} = 1$. Hence the order of $a b$ is precisely $x y$: for elements with coprime orders, the order of their product is equal to the product of their orders.

More generally, let $d = \gcd(x,y)$. Then $x | k y$ and $y | k x$ implies that $k$ must be a multiple of $(x/d)(y/d)$. If $z$ is the least common multiple of $x$ and $y$, which we can compute by $z = x y / d$, then $(a b)^z = 1$. All we can say at the moment is that the order of $a b$ is a multiple of $x y / d^2$ and divides $x y / d$.

The RSA Problem

Suppose we are given positive integers $e, N$, and $a^e \pmod{N}$ for some unit $a$. How can we recover $a$?

One strategy is to find an integer $d$ such that $a^{d e} = a \pmod{N}$. By Euler’s Theorem, $d$ will satisfy this equation if $d e = k \phi(N) + 1$ for some $k$. In other words, we compute

\[ d = e^{-1} \pmod{\phi(N)} \]

and compute $(a^e)^d$ to recover $a$.

However it is not known how to compute $\phi(N)$ from $N$ without factoring $N$, and it is not known how to factor large numbers efficiently.