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.

  • $\begingroup$ What do you mean by "tried"? The equation $a^{(p-1)/2}\overset{\text?}=1$ does not necessarily hold. $\endgroup$ – yyyyyyy Feb 8 '15 at 22:34
  • $\begingroup$ In particular, what is $g^{x(p-1)/2}$ if $x$ is even? What is it if it is odd? $\endgroup$ – poncho Feb 8 '15 at 22:35
  • $\begingroup$ 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! $\endgroup$ – Robert NACIRI Feb 8 '15 at 22:45
  • $\begingroup$ 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 $\endgroup$ – mike russel Feb 8 '15 at 22:47
  • $\begingroup$ What happens when x is odd? $\endgroup$ – 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^*$).

  • $\begingroup$ 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 $\endgroup$ – mike russel Feb 9 '15 at 0:06
  • $\begingroup$ You don't care what it is equal to. ;) What is important is what it is not equal to. $\endgroup$ – fkraiem Feb 9 '15 at 0:12
  • $\begingroup$ By the way, $g^{p-1} = 1$ is true for any $g$. The fact that $g$ is a generator implies something more than that. $\endgroup$ – fkraiem Feb 9 '15 at 0:17
  • 1
    $\begingroup$ @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$. $\endgroup$ – fkraiem Feb 9 '15 at 0:29
  • 1
    $\begingroup$ @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$. $\endgroup$ – fkraiem Feb 9 '15 at 0:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.