Exercise 2.9.5* (Discrete logarithm in $2$-groups)

Proof. Let $z$ be a quadratic non residue of $p$, and put $c\equiv z^m(\mathit{mod}p)$. Then the order of $c$ is $2^k$. Indeed,

so that the order of $c$ is a divisor of $2^k$. Moreover

since $z$ is a quadratic nonresidue. This shows that the order of $c$ modulo $p$ is $2^k$.

Write $\xi =[c]$ the class of $c$ in $∕p$. The order of $\xi$ in the group ${(∕p)}^{\text{∗}}$ is $2^k$, so that the cyclic subgroup $G=⟨\xi ⟩=\{1,\xi ,{\xi }^2,\dots ,{\xi }^{2^k-1}\}$ has $2^k$ elements.

We prove that $G$ is also the set $H$ of the elements of ${(∕p)}^{\text{∗}}$ whose order is a power of $2$.

To prove this, note first that $G\subseteq H$, because the order of $\xi$ is $2^k$, thus the order of ${\xi }^j$ divides $2^k$, thus is a power of $2$ for all $j$.

Let $\gamma$ be a generator of ${(∕p)}^{\text{∗}}$. If $y\in {(∕p)}^{\text{∗}}$, then $y={\gamma }^t$ for some integer $t$. If $y\in H$, then $y^{2^l}=1$ for some $l\ge 0$, thus ${\gamma }^{t{2}^l}=1$. Since the order of $\gamma$ is $p-1=m{2}^k$, $m{2}^k\mid t{2}^l$, therefore $m\mid t{2}^l$ where $m\wedge 2^l=1$, hence $m\mid t$.

Conversely, if $m\mid t$, then $t=\mathit{qm}$ for some integer $q$, and

thus the order of $y$ is a power of $2$, and $y\in H$. We have proved that

Therefore $H=⟨{\gamma }^m⟩$, where the order of ${\gamma }^m$ is $2^k$, so that $H$ is a subgroup of order $2^k$. Since $G\subseteq H$, where $|G|=|H|$, we obtain $G=H$.

Suppose that $n\not\equiv 1(\mathit{mod}p)$, and that the order of $n$ modulo $p$ is a power of $2$, say $2^{k^{\prime }}$, where $k^{\prime }\le k$. Then $[n]\in H=G=⟨\xi ⟩$, thus $[n]={\xi }^u={[c]}^u$, so that

(All these facts are proven in the text p. 112 and p. 114.)

Now put $n^{\prime }\equiv n{\bar{c}}^{2^{k-k^{\prime }}}(\mathit{mod}p)$, where $c\bar{c}\equiv 1(\mathit{mod}p)$, i.e.

Since the order of $\xi$ is $2^k$, the order of ${\xi }^{-1}$ is also $2^k$, thus the order of ${({\xi }^{-1})}^{2^{k-k^{\prime }}}$ is $2^{k^{\prime }}$, which is also the order of $[n]$. By theorem 2.45, the order of $[n^{\prime }]=[n]{({\xi }^{-1})}^{2^{k-k^{\prime }}}$ is $2^{k^{″}}$ for some $k^{″}<k^{\prime }$.

Put $n_0=n,k_1=k^{\prime },n_1=n^{\prime },k_2=k^{″}$. If $k_2>0$, write $n_2\equiv n_1{\bar{c}}^{2^{k-k_2}}(\mathit{mod}p)$, so that the order of $n_2$ is $2^{k_3}$ for some $k_3<k_2$. We continue in this manner, while $k_i\ne 0$. Since the sequence $(k_i)$ is decreasing, there is some rank $d$ for which $k_{d+1}=0$ (there are at most $k$ steps in this algorithm). Then

where $2^{k_{i+1}}$ is the order of $n_i$ for all $i$. In particular $n_d$ has order $2^{n_{d+1}}=2^0=1$, thus $n_d\equiv 1(\mathit{mod}p)$.

Therefore

since $n_d\equiv 1(\mathit{mod}p)$. So

By definition of $u$, $0\le u<2^k$. Moreover,

so $0\le 2^{k-k_1}+2^{k-k_2}+\cdots +2^{k-k_d}<2^k.$ The unicity of $u$ such that $n\equiv c^u(\mathit{mod}p),0\le u<2^k$, shows that

Here $k-k_1<k-k_2<\cdots <k-k_d$, therefore $2^{k-k_1}+2^{k-k_2}+\cdots +2^{k-k_d}$ is the binary expansion of $u$. □