Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

closed as unclear what you're asking by CodesInChaos, e-sushi, otus, poncho, fgrieu Oct 22 '14 at 22:15

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question.If this question can be reworded to fit the rules in the help center, please edit the 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
Right, the newest interpretation of the question doesn't make sense again. Are you asking how many pairs $(a,b)$ there are such that $E$ is an elliptic curve? – figlesquidge Dec 5 '13 at 18:19

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

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