Counting the Number of Points on Elliptic Curve over finite field

cryptographyelliptic-curvesfinite-fieldsnumber theory

I'm studying elliptic curves and have stumbled upon this problem:

Let p be a prime number such that 3 does not divide p − 1. Let E be an elliptic curve defined like this:

$E = \{ (x,y ) \in \mathbb{F}_{p}^2 | \quad Y^{2} = X^{3} + 7 \}
.$

The Goal is to compute $| E(\mathbb{F}_{p})|$.

I've seen Hasse's bound:
$|E(\Bbb F_p)| \geq p+1-2\sqrt p > 1, \quad\forall p \geq 5$

And that the number of points is $N=1+\sum_{x\in\Bbb{F}_p}\left(1+\left(\frac{x^3+ax+b}p\right)\right).$

(I thought that for $p > 3$, $p$ can be written as $p = 3*k + 2$ for some $k \in \mathbb{Z}$ since p-1 is not divisible by 3. However i don't see how i could use this.)

Has anyone got an idea how to compute the number of points?

Best Answer

You made all the relevant observations, so let me outline an answer in the form of exercises for you.

Let $p$ be an odd prime with $p \equiv 2 \pmod{3}$.

Exercise 1: show that the map $\varphi: \mathbf F_p^\times \rightarrow \mathbf F_p^\times$ given by $\varphi(x) = x^3$ is an automorphism.

$\,$

Exercise 2: use exercise 1 to show that $$\sum_{x \in \mathbf F_p}\left(\frac{x^3 + 7}{p}\right) = \sum_{x \in \mathbf F_p}\left(\frac{x}{p}\right) = 0 $$

$\,$

Exercise 3: conclude that $|E(\mathbf F_p)| = p+1$.

Can you solve it now?

Related Question