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 = \, &lt; \negmedspace h \negmedspace &gt;$ 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?

Note that this is the idea underlying the Pohlig-Hellman algorithm, so it may help to have a look at that.