1
$\begingroup$

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.

$\endgroup$
7
  • $\begingroup$ What do you mean by "tried"? The equation $a^{(p-1)/2}\overset{\text?}=1$ does not necessarily hold. $\endgroup$
    – yyyyyyy
    Commented Feb 8, 2015 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
    Commented Feb 8, 2015 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$ Commented Feb 8, 2015 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$ Commented Feb 8, 2015 at 22:47
  • $\begingroup$ What happens when x is odd? $\endgroup$ Commented Feb 8, 2015 at 23:12

1 Answer 1

2
$\begingroup$

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^*$).

$\endgroup$
8
  • $\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$ Commented Feb 9, 2015 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
    Commented Feb 9, 2015 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
    Commented Feb 9, 2015 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
    Commented Feb 9, 2015 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
    Commented Feb 9, 2015 at 0:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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