I'm trying to understand Schoofs algorithm for determining $\#E(F_P)$ of an Elliptic curve $y^2 = x^3 + ax + b$ over $F_P$. For this I'm looking at the implementation of MIRACL: https://github.com/CertiVox/MIRACL/blob/master/source/curve/schoof.cpp At line 1289 the interesting part starts. Two points $(XT, YT, ZT)$ and $(XPP, YPP, 1)$ are added using elliptic_add(). All variables (XT, YT, ZT, XPP, YPP) are polynomials modulo a division polynomial.

I've read this here, but it didn't help me understand my particular problem: Polynomial representation of elliptic curve points (Frobenius Endomorphism)

I would like to double check the results and convert a point to affine representation so I'm able to check if it's on the curve. For this, I've tried the math on a small example:

Consider the curve with:

$a = 5,\ \ \ \ b = 3,\ \ \ \ p = 11267167828871254889$

Then for a certain division polynomial which I perform modular arithmetic against:

$\psi = 3 x^4 + 30 x^2 + 36x + 11267167828871254864$

I do get the following:

$XT = 3755722609623751763x^3 + 360x^2 + 324x + 11267167828871254689$

$YT = 3755722609623752459x^3 + 6400x^2 + 1251907536541253001x + 11267167828871250673$

$ZT = 2x^3 + 10x + 6$

I've tried calculating the point

$(x, y) = (\frac{XT}{ZT^2 \mod \psi}, \frac{YT}{ZT^3 \mod \psi})$

But the result is not a point on the curve. I cannot seem to get the actual affine point. The code clearly says that the tuple $(XT, YT, ZT)$ refers to one particular point on the curve (line 202ff). How can I determine which one it is in my example?

  • $\begingroup$ Hmm. I don't have the time to check anything, but are you sure you've got the correct mapping from projective coordinates to affine ones? At least two systems are in use in EC crypto. With the usual (homogeneous) projective coordinates we get, if I correctly guessed what your notation means, $x=XT/ZT$, $y=YT/ZT$, but only in (what I think was once called superprojective, but nowadays seems to be called) the Jacobian coordinate system we have $x=XT/ZT^2$, $y=/ZT^3$. $\endgroup$ – Jyrki Lahtonen Mar 3 '16 at 13:18
  • $\begingroup$ (cont'd) The Jacobian system is even more efficient for some elliptic curve primitive operations, and thus gained popularity for some implementations. Basically I am worried that if you use code from two different sources based on different coordinate systems, then the operations will not mesh. $\endgroup$ – Jyrki Lahtonen Mar 3 '16 at 13:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.