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

  • 2
    $\begingroup$ Have you looked up Schoof's algorithm? $\endgroup$ – Squeamish Ossifrage May 10 '18 at 19:04
  • 4
    $\begingroup$ 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. $\endgroup$ – 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.

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

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.