# LSB of the Exponent in the DL Problem Can Be Efficiently Computed for Groups of Even Order

I am studying a script on the mathematical foundations of cryptography as part of which I am currently trying to wrap my head around some basic cryptographic reductions. I am stuck on one problem that I would like to request some help / advice on how to proceed:

Consider the (D)iscrete (L)ogarithm problem for a group $H = \, < \negmedspace h \negmedspace >$ of even cardinality $\lvert H \rvert = 2 n$. Show that there exists an efficient algorithm that computes the LSB of $x$ in the DL problem $y = h^x$.

So far the only thing I managed to come up with is the following: We can determine the order of $y$ and find $c$ s.t. $y^c = h^{x c}= 1$. Since the group caridnality is even we conclude that $x c = m 2 n$. If $c$ is odd we can therefore conclude that $x$ must be even and hence the LSB of $x$ is zero. How can I proceed from here? The only additional insight I can present is, that due to Lagrange, we know that $c$ divides $2 n$.

Write $x=x_0+2x_1$ for $x_0\in\left\{0,1\right\}$, so that the goal becomes determining $x_0$. Now compute $y^n$ (in terms of $h$, $x_0$ and $x_1$), and determine its order. What happens when $x_0=0$ and when $x_0=1$? Can we easily differentiate between them?
• Yes it is indeed an elegant argument, there is still much satisfaction to be gained by generalizing this! Can you find the two least significant bits when $|H|=2^2n$? How about an analogue when $|H|=2^{1000}n$? How about $|H|=p^mn$ for some prime $p$ and integer $m$? You are then very close to explaining how the Pohlig-Hellman algorithm works, which is great! Nov 26, 2016 at 13:41