Introduction to Cryptography with Coding Theory, 3rd Edition

18.3 Exercises

1. Let $\alpha$ be a primitive root for the prime $p$. This means that the numbers $1\text{,}\alpha \text{,}{\alpha }^2\text{,}{\alpha }^3\text{,}\dots \text{,}{\alpha }^{p-2}(\text{mod}p)$ yield all of the nonzero congruence classes mod $p$.

   1. Let $i$ be fixed and suppose $x^2\equiv {\alpha }^i(\text{mod}p)$ has a solution $x$. Show that $i$ must be even. (Hint: Write $x\equiv {\alpha }^j$ for some $j$. Now use the fact that ${\alpha }^k\equiv {\alpha }^l(\text{mod}p)$ if and only if $k\equiv l(\text{mod}p-1)$.) This shows that the nonzero squares mod $p$ are exactly $1\text{,}{\alpha }^2\text{,}{\alpha }^4\text{,}{\alpha }^6\text{,}\dots (\mathrm{m}\mathrm{o}\mathrm{d}p)$, and therefore $\alpha \text{,}{\alpha }^3\text{,}{\alpha }^5\text{,}\dots$ are the quadratic nonresidues mod $p$.

   2. Using the definition of primitive root, show that ${\alpha }^{(p-1)/2}\cancel{\equiv }1(\text{mod}p)$.

   3. Use Exercise 15 in Chapter 3 to show that ${\alpha }^{(p-1)/2}\equiv -1(\text{mod}p)$.

   4. Let $x\cancel{\equiv }0(\text{mod}p)$. Show that $x^{(p-1)/2}\equiv 1(\text{mod}p)$ if $x$ is a quadratic residue and $x^{(p-1)/2}\equiv -1(\text{mod}p)$ if $x$ is a quadratic ...