Breaking ElGammal encryption of two different mesagges 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.
Further hint: suppose we computed $q = (p-1)/2^\lambda$ odd, and given $(u_1, v_1) = (g^r, m y^r)$, we compute $(g^r)^q, (m y^r)^q$.  Once we have done that, how can you distinguish the $m=1$ and $m= -1$ cases?