Let $p > 3$ be a prime such that $p \equiv 2 \pmod 3$. Define the elliptic curve $E$ over $\mathbb{F}_p$ by $y^2 = x^3 + 1$. Prove that $E(\mathbb{F}_p)$ consists of $p+1$ points.

Using Fermat's little theorem you can prove that $x^3 + 1$ is a bijection on $\mathbb{F}_p$. Hence, $$\#E(\mathbb{F}_p) = \#\{(x,y) \in \mathbb{F}_p^2 : y^2 = x^3 + 1\} + \#\{\infty\} = \#\{(x,y) \in \mathbb{F}_p^2 : y^2 = x\} + 1.$$ But then I am stuck trying to prove that $y^2 = x$ has $p$ solutions $(x,y) \in \mathbb{F}_p^2$.

  • $\begingroup$ How this is true :$$\#\{(x,y) \in \mathbb{F}_p^2 : y^2 = x^3 + 1\} + \#\{\infty\} = \#\{(x,y) \in \mathbb{F}_p^2 : y^2 = x\} + 1.$$ $\endgroup$ – curious Dec 3 '13 at 11:47
  • $\begingroup$ @curious Consider the equations $y^2 = x^3 + 1$ and $y^2 = z$ over $\mathbb{F}_p$. The map $(x,y) \mapsto (z = x^3 + 1,y)$ is a bijection between their respective solution sets, because $x \mapsto x^3 + 1$ is a bijection on $\mathbb{F}_p$. In particular, the equations have the same number of solutions. $\endgroup$ – Ricardo Buring Dec 3 '13 at 19:08

If any of $x,y$ is zero, then $x=y=0$ is the only solution pair. Otherwise, there are $\displaystyle\frac{p-1}2$ quadratic remainders $x$ and for each one exactly $2$ pieces of $y$'s belong ($\pm y$ once $y^2\equiv x$). It's altogether $1+2\cdot\displaystyle\frac{p-1}2=p$.

Or, an even easier approach: for each $y\in\Bbb F_p$ there is exactly one such $x$.

  • $\begingroup$ Your easy approach is nice. Thank you. $\endgroup$ – Ricardo Buring Nov 11 '12 at 14:33

It is much more easy to prove. Like known from RSA the equation const = x^3 mod n has exactly one solution for x, namely x = const ^ d mod n there d = inv(3, phi(n)).

The only condition is, geatest common divisor gcd(3, phi(n)) must be one. In our case Euler's totient function phi equals p-1. The condition is true since p = 2 mod 3,

since p - 1 = 1 mod 3 it follows gcd(3, p-1) = 1.

For y^2 unequal to zero we get two points for a specific value of y. Since y^2 minus one has (p-1)/2 different values. we totally get (p - 1) points plus the point for y = 0 the point (p-1, 0) and the point at infinity. So, we have a total of (p - 1) + 1 + 1 = p + 1 points.


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.