1
$\begingroup$

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.

$\endgroup$
0

1 Answer 1

2
$\begingroup$

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

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)$

enter image description here

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;

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.