MATH 470 Lecture 13

« previous | Tuesday, February 26, 2013 | next »

Lagrange's Theorem

(special case) offers a way to check if $a$ is a generator for $(\mathbb {Z} /p\mathbb {Z} )^{*}$

If $p$ is prime and $a\in \left(\mathbb {Z} /p\mathbb {Z} \right)^{*}$ ,

Then $\mathrm {ord} _{p}(a)\mid (p-1)$ , where $\mathrm {ord} _{p}(a)$ is the smallest exponent $e\neq 0$ with $a^{e}\equiv 1{\pmod {p}}$ .

Proof. Suppose $k=\mathrm {ord} _{p}(a)$ . Consider $\ell =\mathrm {GCD} (k,p-1)$ .

By the Extended Euclidean Algorithm, there are $x,y\in \mathbb {Z}$ with $k\,x+(p-1)\,y=\ell$ .

So then $a^{\ell }\equiv a^{k\,x+(p-1)y}\equiv 1{\pmod {p}}$ . Since $\ell \mid k$ (since $k=\mathrm {ord} _{p}(a)$ , we must have $\ell \geq k$ . By construction, $\ell \mid k\implies \ell =k$ , so $k\mid (p-1)$ .

Q.E.D.

Corollary

If $p$ is prime and $a\in (\mathbb {Z} /p\mathbb {Z} )^{*}$ and $a^{\frac {p-1}{q}}\not \equiv 1{\pmod {p}}$ for all primes $q\mid (p-1)$ ,

Then $a$ is a generator of $\mathbb {Z} /p\mathbb {Z} )^{*}$ .

In particular, given a list $\{a_{1},\ldots ,a_{k}\}$ of all primes dividing $p-1$ , you can check the preceding condition in time $O((\log {p})^{4})$

Note:

Life is cruel: you usually do NOT have such a list.
If $p-1$ is a product of small primes (to any powers), then life is good!

Proof. We must show that $\mathrm {ord} _{p}(a)=p-1$ . By Lagrange's theorem, $\mathrm {ord} _{p}(a)\mid (p-1)$ .

So we need to rule out $\mathrm {ord} _{p}(a)$ being a divisor of $p-1$ other than $p-1$ .

If $p-1=q_{1}^{e_{1}}\dots q_{k}^{e_{k}}$ is the factorization of $p-1$ , then any $d<p-1$ dividing $p-1$ must divide ${\tfrac {p-1}{q_{1}}}$ or ${\tfrac {p-1}{q_{2}}}$ or ... or ${\tfrac {p-1}{q_{k}}}$ .

Now $a^{\frac {p-1}{q}}\not \equiv 1{\pmod {p}}$ for all $q\mid (p-1)$ is equivalent to $a^{\frac {p-1}{q_{1}}}\not \equiv 1{\pmod {p-1}}$ , ..., $a^{\frac {p-1}{q_{k}}}\not \equiv 1{\pmod {p-1}}$ . So if $\mathrm {ord} _{p}(a)<p-1$ , it would divide one of ${\tfrac {p-1}{q_{1}}}$ or ... or ${\tfrac {p-1}{q_{k}}}$ , which is impossible.

Therefore $\mathrm {ord} _{p}(a)=p-1$ .

Q.E.D.

Complexity Bounds

By Theorem 5.4.1 (of Bach and Shallit), computing $a^{e}{\pmod {n}}$ takes $O((\log {e})(\log ^{2}{n}))$ bit operations. So computing $a^{\frac {p-1}{q}}{\pmod {p}}$ takes $O((\log {p})^{3})$ bit operations. By problem 5 of homework 6, the number of primes dividing $p-1$ is $O(\log {p})$