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 curve with equation $y^2=x^3+ax+b$, I want to find the number of pairs $(a,b)\in \mathbb{F}_p \times \mathbb{F_p}$ NOT on the curve. How do I do it?

I have an intuition that it is $p$, but don't know how to rigorously show it.

share|improve this question
Your notation is confusing since you use $a,b$ as curve parameters and as the coordinates of a point. –  CodesInChaos Dec 5 '13 at 17:01
Actually, it is still confusing since the notation $E({\mathbb F}_p)$ is typically used for denoting the set of points $(r,s)\in {\mathbb F}_p^2$ satisfying the curve equation $E$ (plus the point at infinity). –  DrLecter Dec 5 '13 at 17:07
Do you mean: Given an elliptic curve with equation $y^2=x^3+ax+b$, and i want to find the number of points $(r,s)\in \mathbb{F}_p^2\cup\{\infty\}$ NOT on the curve? –  figlesquidge Dec 5 '13 at 17:12
i believe you get the idea of the problem(Basically to prove there are $p$ points which belonging to the field not on the curve)? Could you tell me the technique to solve it? –  user12345 Dec 5 '13 at 17:12
yea i guess @figlesquidge is right! –  user12345 Dec 5 '13 at 17:12

1 Answer 1

At this point in time the question asked how many points were there that were not on the curve

Whats wrong with doing $p^2 +1 - |E(\mathbb{F}_p)|$?

Taking an example from wikipedia (who reference #1):

The curve defined by $$ y^2 = x^3 - x $$ over $\mathbb{F}_{71}$ has $72$ points ($71$ affine points including $(0,0)$ and one point at infinity)

So there are $70*71$ points not on the curve - far more than just $71$.

Ref #1: Koblitz, Neal (1994). "Chapter 6". A Course in Number Theory and Cryptography. Graduate Texts in Mathematics 114 (2nd ed.). Springer-Verlag. ISBN 0-387-94293-9)

share|improve this answer
i think the question actually meant (a,b) and not (r,s) if it was (r,s) i think it is trivial as u say! –  user12345 Dec 5 '13 at 17:48
Right :/ Well I've Commented on the question, and will leave this answer in case the question changes back again! –  figlesquidge Dec 5 '13 at 18:20

Your Answer


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.