I'm taking a cryptography class and this algebra problem was posed as optional homework:
Prove that if $P = 2^m + 1$ is a prime and $g$ is a generator of its multiplicative group then $Prob((g^x \bmod P) \bmod 2 = x \bmod 2) = \frac{1}{2}$.
I experimented a bit and confirmed the result for $P = 17$ and $P = 257$. The parity of $g^x \bmod P$ looks rather random so I would guess that the argument should be somewhat "global" rather than constructive. I also noticed experimentally that:
If $x \in \langle g^{2^k} \rangle$ where $ 1\leq k < m$ then $Prob(x \bmod 2 = 0) = \frac{1}{2}]$.
This seems significant, but I can't see why it happens. Note that proving this for $k = 1$ is actually sufficient for my question.
I am probably missing some basic group theory knowledge.
Thank you!
Later Edit: Changed some notation.
Since $g^{(p-1)/2}\equiv -1\pmod p$, we have \begin{align} g^{x+(p-1)/2}\bmod p &=p-(g^x\bmod p)\\ &\equiv 1-(g^x\bmod p)\pmod 2 \end{align} Thus if $\varphi(x)=((g^x\bmod p)-x)\bmod 2$, then $$\varphi\left(x+\frac{p-1}2\right)=1-\varphi(x)$$ hence the function $x\mapsto x+\frac{p-1}2$ induces a bijection $$\varphi^{-1}\{0\}\to\varphi^{-1}\{1\}$$ thus proving $$\mathrm P[\varphi(x)=0]=\frac 12$$