# How Can I Know the Number of Points on an elliptic curve?

If I have the following Elliptic Curve: $$E: y^2 ≡ x^3 + 2x + 2 \mod 17$$

How Can I calculate the Number of Points on this elliptic curve $$\#E$$ ?

and how can I invest the following law which calculates the Number of Points on an Elliptic curve NPE:

$$NPE=1+p+\sum_{x=1}^{p-1} \frac{f(x)}{p}$$

• Have you looked up Schoof's algorithm? – Squeamish Ossifrage May 10 '18 at 19:04
• For the simple elliptic curve $E$, what's wrong with finding all the points on the curve and counting them? Since things are computed modulo 17, there are only 17 values of $x$ to try and compute $x^3+2x+2\bmod17$. Then finding the corresponding value of $y$ (if any) can be done by way of a table of squares modulo 17. The whole thing seems doable with with pen and paper in minutes. – fgrieu May 10 '18 at 20:40

As the astute commenters pointed out, small cases can be done by hand, while Schoof's algorithm can be used for large fields.

By the way, there is the well known bound $$q+1-2\sqrt{q} \leq \#E \leq q+1+2\sqrt{q}$$ on what you call NPE, due to Hasse-Weil, for curves over $\mathbb{F}_q.$ If $q$ is prime, the inequality is strict.

• Shouldn't that be $\leq$? – yyyyyyy May 10 '18 at 22:31
• I was thinking of prime $q$ whereby it is a strict inequality, but you are right in general. – kodlu May 11 '18 at 5:45
• I guess $\#E$ includes the point at infinity? Note: If $q$ is not a square (including prime), the inequality obviously is strict. – fgrieu May 11 '18 at 8:41