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

- limited by Hasse's Theorem: $N - (q+1)| le 2 sqrt{q}$ over finite field with $q$ elements.
- Or, exactly found by Schoof's algorithm, In the paper Counting Points on Elliptic Curves over Finite Fields, published in 1985,
- Or, the improved version Schoof–Elkies–Atkin algorithm

_{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;

- Integral Points in Arithmetic Progression on $y^2=x(x^2-n^2)$, by Bremner, Silverman, and Tzanakis, 2000.

Answered by kelalaka on December 21, 2021

1 Asked on December 31, 2021 by kaa

0 Asked on December 31, 2021 by sunitha-tappari

0 Asked on December 28, 2021 by dawnforce

2 Asked on December 26, 2021 by maarten-bodewes

0 Asked on December 24, 2021

2 Asked on December 21, 2021 by skaht

1 Asked on December 21, 2021 by kmart875

1 Asked on December 19, 2021 by sanket1729

1 Asked on December 19, 2021 by vivekanand-v

2 Asked on December 17, 2021

0 Asked on December 17, 2021

3 Asked on December 14, 2021 by antonpug

1 Asked on December 14, 2021 by beroal

0 Asked on December 8, 2021

Get help from others!

Recent Questions

- How Do I Get The Ifruit App Off Of Gta 5 / Grand Theft Auto 5
- Iv’e designed a space elevator using a series of lasers. do you know anybody i could submit the designs too that could manufacture the concept and put it to use
- Need help finding a book. Female OP protagonist, magic
- Why is the WWF pending games (“Your turn”) area replaced w/ a column of “Bonus & Reward”gift boxes?
- Does Google Analytics track 404 page responses as valid page views?

Recent Answers

- haakon.io on Why fry rice before boiling?
- Lex on Does Google Analytics track 404 page responses as valid page views?
- Peter Machado on Why fry rice before boiling?
- Jon Church on Why fry rice before boiling?
- Joshua Engel on Why fry rice before boiling?

© 2022 AnswerBun.com. All rights reserved. Sites we Love: PCI Database, MenuIva, UKBizDB, Menu Kuliner, Sharing RPP, SolveDir