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$ 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$ Feb 8 '15 at 22:47
  • $\begingroup$ What happens when x is odd? $\endgroup$ 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$ 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.