# Find Consecutive X-Coordinate algorithm

Cryptography Asked by kmart875 on December 21, 2021

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}, mgeq 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;

Answered by kelalaka on December 21, 2021

## Related Questions

### Binomial distribution sampling – concrete example

0  Asked on January 4, 2022

### Using xor encryption in the following use case

1  Asked on December 31, 2021 by kaa

### How to justify the lightweight symmetric PRESENT encryption algorithm is more secure?

0  Asked on December 31, 2021 by sunitha-tappari

### Difference Between an Authentication Token and an OTP (One Time Password)

0  Asked on December 28, 2021 by dawnforce

### Using XOR to derive a data key for ECIES

2  Asked on December 26, 2021 by maarten-bodewes

### Digital Signature or MAC Yielding Non-Binary Verification Predicate

0  Asked on December 24, 2021

### Computing PGP ed25519 and curve25519 keygrips?

2  Asked on December 21, 2021 by skaht

### Find Consecutive X-Coordinate algorithm

1  Asked on December 21, 2021 by kmart875

### Is there any proof for ECDSA signature algorithm?

1  Asked on December 19, 2021 by sanket1729

### What basic knowledge is required to understand SIKE?

1  Asked on December 19, 2021 by vivekanand-v

### Why we can’t implement AES 512 key size?

3  Asked on December 17, 2021 by hamedb71

### MD5 – Chosen Prefix Collision Attack

1  Asked on December 17, 2021

### Does selectively generating keypairs with particular public-key hash prefix weaken the security?

2  Asked on December 17, 2021

### Difference between polynomial embedding and canonical embedding

0  Asked on December 17, 2021

### How can Cipher Block Chaining (CBC) in SSL be attacked?

3  Asked on December 14, 2021 by antonpug

### Subset Sum Hashes

1  Asked on December 14, 2021 by lev-knoblock

### Why is this authenticated Diffie–Hellman key exchange insecure?

1  Asked on December 14, 2021 by beroal

### Homomorphic encryption scheme for modulo reduction

0  Asked on December 8, 2021

### Can we say that password authentication contains registration phase, authentication phase and authenticated key exchange phase?

0  Asked on December 6, 2021 by z-p

### LWR parameter estimation

0  Asked on December 4, 2021 by mev