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 from 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 theorems are special cases of Lagrange’s Theorem from group theory. (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.


Ben Lynn blynn@cs.stanford.edu 💡