# Finding $x$'s parity in the discrete log problem

Suppose $p$ is prime, and $g, a\in\mathbb F_p$ are given elements with $g$ a primitive root. The discrete log problem poses the task of finding an integer $x$ such that $g^x=a$. Show that even if $x$ cannot be recovered, one can check if $x$ is odd or even by inspecting the element $a^{(p-1)/2}$.

I'm not sure how to approach this question. I tried $g^{x(p-1)/2} = a^{(p-1)/2} = 1$.

Any help would be appreciated! Thanks.

• What do you mean by "tried"? The equation $a^{(p-1)/2}\overset{\text?}=1$ does not necessarily hold. – yyyyyyy Feb 8 '15 at 22:34
• In particular, what is $g^{x(p-1)/2}$ if $x$ is even? What is it if it is odd? – poncho Feb 8 '15 at 22:35
• The question is strongly connected with Legendre Symbol of a, as you observe it. If Legendre symbol of a is +1, then x is even! – Robert NACIRI Feb 8 '15 at 22:45
• if x is even then 2 divides it but I don't know what that means. does it imply that it's equal to 1? by fermat's little theorem – mike russel Feb 8 '15 at 22:47
• What happens when x is odd? – mike russel Feb 8 '15 at 23:12

Claim. $a^{(p-1)/2} = 1$ if and only if $x$ is even.
Proof. If $x$ is even, let $x = 2y$. Then $$a^{(p-1)/2} = (g^x)^{(p-1)/2} = g^{2y(p-1)/2} = (g^{p-1})^y = 1^y = 1.$$
If $x$ is odd, let $x = 2y+1$. Then $$a^{(p-1)/2} = g^{(2y+1)(p-1)/2} = \dots$$ (remember here that $g$ is a generator of $\mathbf{F}_p^*$).
• If x is odd, we are left with $g^{(p-1)/2}$. However i fail to understand what that is equal to. I know $g^{(p-1)} = 1$ since $g$ is a generator – mike russel Feb 9 '15 at 0:06
• By the way, $g^{p-1} = 1$ is true for any $g$. The fact that $g$ is a generator implies something more than that. – fkraiem Feb 9 '15 at 0:17
• @Bren2010 What are you talking about? We are working in the full group $\mathbf{F}_p^*$, which in your example has order $10$, not $5$. – fkraiem Feb 9 '15 at 0:29
• @mikerussel Oh and by the way, the fact that $a^{(p-1)/2} = -1$ if $x$ is odd follows simply from what you have found. You have $a^{(p-1)/2} = g^{(p-1)/2}$, so $(a^{(p-1)/2})^2 = g^{p-1} = 1$, meaning that $a^{(p-1)/2}$ is a root of the polynomial $X^2-1$. Since we are over a field, this polynomial has at most two roots, which are easily seen to be $1$ and $-1$. Since $a^{(p-1)/2}$ is not $1$, it must be $-1$. – fkraiem Feb 9 '15 at 0:42