# Find Consecutive X-Coordinate algorithm

The question is as follows: Is there an algorithm to calculate a $$(x,y)$$ pair which is consecutive to an existing $$x$$-Coordinate on an elliptic curve?

Background Information for the curve:

Known Values: Prime Curve ($$p$$), Prime Multiplier ($$N$$), Trace ($$P-N$$), Curve is Half. Multipliers $$(M_1 + M_2) = N$$, $$y$$ Coordinates + Inverse $$Y$$ Coordinate = $$P$$.

Any help is greatly appreciated.

Update: An algorithm to calculate a $$(x,y)$$ pair and integer multiplier which is consecutive to an existing $$x$$-coordinate on the curve.

Let $$P = (x,y)$$ be a point on the curve $$E$$ with the $$y^2 = x^3 + ax + b$$ with Weierstrass equation over the prime field $$\operatorname{GF}(p)$$1, i.e. it satisfies the curve equation.

The consecutive $$x$$-coordinate point can be found with the below algorithm.

for i from 1 to number_of_poinst_on_the_curve
temp = x + i mod p
if  (temp, y) satisfies the curve equation
return (temp,y')
else
continue
throw no_consecutive_element

• The $$\bmod p$$ is necessary since we don't want our $$x$$ has value out of the possible space.

• $$y'$$ is one of the two possible solitons to the $$y^2$$, except when $$y=\mathcal{O}$$, the point at the infinity. The educative details of finding the square root in modular arithmetic can be found on Fgrieu's latest answer;

Is it possible to compute the y-coordinate of a point on SECP256K1, given only the x-coordinate

• The algorithm will terminate since the EC has a finite number of points. The number of points can be

1 This is used to simplify the algorithm. EC doesn't need to be defined over a prime finite field. In Cryptography, we use the general case of Finite Fields $$\operatorname{GF}(q=p^m), m \in \mathbb{Z}, m\geq 1$$. Expect the prime field, the other fields have different representation for the elements.

For $$y^2 = x^3 + x^2 + x$$ over $$GF(131)$$

E = EllipticCurve(GF(131),[0,1,0,1,0])

P=E.lift_x(0) #lift can throw an error if there is no point with the given input
#tested before that there is a point with x=0

plotE = E.plot()

for t in srange(1,129):
try:
R =  E.lift_x(t)
plotE += line([P.xy(),R.xy()],color='red')
P = R
except ValueError:
pass
plotE


update

Though I don't see the direct effect on Cryptography, there are academic works on this;