I'm trying to understand the Schoof algorithm for counting the number of points on elliptic curves in finite fields. I.e. the most basic algorithm to efficiently determine $\#E(F_p)$.

For literature, I'm referring mostly to the original Schoof (1985) and Gregg Musiker ("Schoofs Algorithm for Counting Points on $E(F_q)$", 2005), who has a nice summary of the Schoof algorithm. As an example implementation I'm looking at MIRACL's schoof.cpp and try to understand how it works in order to replicate the results.

I'm kind of stuck with the Frobenius Endomorphism, i.e. pg. 5 of Musiker, where he introduces the conversion between affine space (i.e. points on the curve) and polynoms. He says that for scalar multiplication of a point $P$ with an scalar $n$, the following holds:

$$nP = \big( \frac{\phi_n(x)}{\psi^2_n(x)}, \frac{\omega_n(x, y)}{\psi^3_n(x, y)} \big)$$

now on the left hand side is a point $(x, y)$, but on the right hand side there is what looks to me like projective representation of coordinates, i.e.

$$\big(\frac{X}{Z^2}, \frac{Y}{Z^3}\big)$$

only that $X$, $Y$ and $Z$ are polynomials this time. How can I convert between affine point representation and polynomial representation of points back and forth?

  • 2
    $\begingroup$ Those are affine coordinates. After all $nP=O$ iff $\psi_n(P)=0$. You only need projective coordinates, when you try to milk everything out of the computational complexity of point multiplication. If you want to speed up point counting, you should consider Schoof-Elkies-Atkin. $\endgroup$ – Jyrki Lahtonen Aug 26 '15 at 12:21

Let $P=(x,y)$ be a point on the elliptic curve which is not the identity. We want to be determine whether $nP=O$, so for this we need to go through the arduous process of explicitly calculating what $nP$ is. This gets very messy considering you need to determine when you are adding a point to itself.

Fortunately, there are these things called division polynomials (the $\psi_n$) which are defined recursively, and then the $\omega_n$ and $\phi_n$ are constructed from these. See this Wikipedia article for the exact definition.

This means we can efficiently compute what the multiple of a point is. They are polynomials since this works for any point, ie given $P=(x,y)$, then $nP$ is given by the formula you have written above.

My point is that this explicitly writes the multiplication by $n$ map as a rational function over the coordinate ring of the elliptic curve.


Your Answer

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

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