Semaev's attack - strange step?

40 Views Asked by At

Semaev's elliptic curve discrete logarithm calculation algorithm (paper) has such first steps:
given P and Q = nP, q - field modulo, E = EllipticCurve(GF(q), [a,b]) # y^2 = x^3 + a*x + b

F = GF(q)
m = # some magic constant, I. Semaev himself made table for some m(q)
V = # sample of GF(q) of size ~q**(1/m)
u, v = random(1,E.order())
R = u*P + v*Q
if R = infinity_point:
   # calculate result as z from b*z + a = 0 (mod q)
else:
   # R = (Rx, Ry)
   if Rx in V:
      # var y
      # solve equation Point(Rx, y) + u*P + v*Q = infinity_point

in the last line we suppose point as (Rx, y), but we already have point R = (Rx, Ry). Does it mean that y = Ry or y = -Ry ?
From Elliptic curve equation: y^2 (I assume only fields of char > 3) = f(x)