4
$\begingroup$

Given an elliptic curve with equation $y^2=x^3+ax+b$, and i want to find the number of points $(a,b)\in E(\mathbb{F}_p)$ where the polynomial has repeated roots, how do i do it? I have an intuition it is $p$, but don't know how to rigorously show it.

Thanks

$\endgroup$
  • $\begingroup$ As usual, Wikipedia is your friend here. $\endgroup$ – pg1989 Dec 5 '13 at 2:12
  • $\begingroup$ i dont think any fancy method is required, or any algorithm is required as what is suggested in wiki! hence i thought any1 here could just explain why it would be $p$ or smth $\endgroup$ – user12345 Dec 5 '13 at 3:46
9
$\begingroup$

An elliptic curve whose polynomial has repeated roots is not in fact an elliptic curve, but a singular cubic curve, as it has a singular point where the group law breaks down. Still, we can remove those broken points and treat the remaining ones as a group. There are 3 possible cases:

  • $y^2 = x^3 \bmod p$. This curve has a triple root, and is isomorphic to the additive group of integers modulo $p$. Therefore the order here is $p$.
  • $y^2 = x^2(x + a) \bmod p$, square $a$. This curve has a double root, and is isomorphic to the multiplicative group of integers modulo $p$. Therefore the order here is $p-1$.
  • $y^2 = x^2(x + a) \bmod p$, nonsquare $a$. This curve has a double root, and is isomorphic to the group of integers in $\mathbb{F}_{p^2}$ of norm $1$. Therefore the order here is $p + 1$.

The full treatment of all these cases is given in several places, e.g. Husemöller or Washington or Silverman.

The simplest case is the first one, where you have $y^2 = x^3$. Here's the outline: show that you can represent a point unambiguously as $t = x/y$ ($t = 0$ for the point at infinity), since $x = 1/t^2$ and $y = 1/t^3$. Since there are as many $t$ as there are field elements, the group size is the same, $p$.

The other two cases follow the similar approach of bijectively encoding a point as a single $\mathbb{F}_p^*$ (or $\mathbb{F}_{p^2}^*$) element.

$\endgroup$

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.