Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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

share|improve this question
    
As usual, Wikipedia is your friend here. –  pg1989 Dec 5 '13 at 2:12
    
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 –  user12345 Dec 5 '13 at 3:46

1 Answer 1

up vote 6 down vote accepted

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.

share|improve this answer
    
thanks a lot for that! –  user12345 Dec 5 '13 at 4:55

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.