I'm stuck with the following problem on ElGammal encryption.
We work on $\mathbb{Z}_{p}^*$ where $p$ is prime and we are given $p$, the generator $g$ of $\mathbb{Z}_{p}^*$ , the public key used $y$ and five encryptions $(u_1,v_1), \cdots, (u_5,v_5)$ where each of them is a encryption of a message $m$ that can be $1$ or $-1$.
Please refer to the second scheme of this question if you need more details on the ElGammal cryptosystem I'm using.
As a hint I'm told to look for a subgroup of index two. I tried to solve the discrete logarithm problem in that subgroup with sage but as this post discusses the complexity is only reduced by a constant so that it is still intractable.
I give you the code I was using in case you have some comments.
F = Integers(p)
gmod = F(g)
q = p // 2
F2 = Integers(q)
gmod2 = F2(g)
ymod2 = F2(y)
gmod2 = F2(g)
ymod2 = F2(y)
Can you figure out how this could be solved?
Edit:
In my case $\frac{p-1}{2}$ is already prime.