1

I'm given an elliptic curve $y^2=x^3+ax+b \in \mathbb{Z}_p[x]$ (with numbers $a,b,p$ not greater than $10^6$).

I would like to find, using the naive approach, the number of affine points on the curve without the point at infinity .

My approach is to go through all $x\in\mathbb{Z}_p$ and check which of them have residue (stored in counter. Since each $x$ has either two or zero residues, I multiply the number of $x$ with residues times 2.

To return the number of affine points, the following method is used:

if isSingular(a,b,p):
    return counter*2+2
return counter*2+1

It seems to work for some cases, but not for others. Is there something special we have to consider for singular curves, and why?

Artem
  • 1,208
  • What does "isSingular" do? What cases do not work? – Álvaro Lozano-Robledo Apr 12 '17 at 15:05
  • isSingular returns true if the elliptic curve is singular and false otherwise (non singular). It uses the $4a^3+27b^2$ to determine this.This question is now solved here: http://crypto.stackexchange.com/questions/46505/number-of-affine-points-on-an-elliptic-curve?noredirect=1#comment103829_46505. The thing that I did not consider is that points that don't have residues can still be on the curve, such as the case when the RHS is equal to zero, ie. $x^3+ax+b = 0 (mod p)$ – Artem Apr 12 '17 at 15:19
  • When $\xi^3+a\xi+b=0$, you have to increase the counter by one, not two. These are the two-division points on the elliptic curve, of which there are at most $3$ (not counting the identity point at infnity). – Lubin Apr 14 '17 at 01:38

0 Answers0