# secp256k1 point density

I am working on a crypto project using the secp256k1 elliptic curve.

I know that I can select a random point $$P = (x, y)$$ from the curve by randomly selecting the first coordinate $$x \in \mathbb{Z}_p$$ (where $$p$$ is the prime of the elliptic curve field $$\mathbb{F}_p$$) and computing the second coordinate $$y$$ using the curve equation $$y^2 = x^3 + 7$$. Because the cofactor of the curve is $$h = 1$$, for every value $$x \in \mathbb{Z}_p$$ that spawns a valid $$y \in \mathbb{Z}_p$$, there is a point on the curve with coordinates $$x, y$$. In case there is a value $$x \in \mathbb{Z}_p$$ for which the curve equation does not find a valid value for $$y \in \mathbb{Z}_p$$, that means there is simply no point on the curve at that $$x$$ coordinate.

I also know that the curve order is $$q$$, with $$q < p$$. That means there exist $$q$$ valid points on the curve, which is less than all the values that $$x$$ could have in $$\mathbb{Z}_p$$.

My question is: How far are points from each other, in respect to the $$x$$ coordinate? What is the largest distance between two points on the curve? Is there any documentation in this regard?

• In which coordinate system? You do understand that the discrete modular curves do not look like curves in the X,Y coordinate system, right? And that although $q < p$, the value of $q$ is only a tiny bit smaller than $p$ for the curves we use for cryptographic operations... – Maarten Bodewes Aug 14 at 11:42
• What exactly do you mean by "distance"? – Conrado Aug 14 at 14:13
• By distance between two points (in respect to the $x$ coordinate) I mean the following: Having two valid points $P_1 = (x_1, y_1)$ and $P_2 = (x_2, y_2)$, with all $x \in (x_1, x_2)$ generating invalid points, the distance between $P_1$ and $P_2$ is $|x_1 - x_2|$. – Hulub Aug 19 at 13:41

I also know that the curve order is $$q$$, with $$q. That means there exist $$q$$ valid points on the curve,

True

which is less than all the values that $$x$$ could have in $$\mathbb{Z}_p$$

Actually, that's less relevant than you think.

• For every $$x$$ value in $$\mathbb{Z}_p$$ that has a valid solution, there are two values of $$y$$ that satisfy the equation (and hence correspond to two points). It's easy to see, if $$(x, y)$$ is a solution, then so is $$(x, -y)$$ (aka $$(x, p-y)$$)

Note: some elliptic curve have 1 or 3 $$x$$ values that correspond to a single $$y$$ value (which is the $$y$$ value 0) - secp256k1 is not one of those curves.

In addition, there is a single 'point of infinity' which doesn't correspond to a solution to the equation, but is thrown in as an additional group element.

Hence, there are exactly $$(q-1)/2$$ $$x$$ values that correspond to (at least one) valid point. Since $$p \approx. q$$, this if you pick an $$x$$ value at random, you have almost exactly a 50% probability of picking one with a solution.

• After some more research, I found out the following: – Hulub Aug 19 at 13:44
• The largest "distance" between two point is not that relevant, because there could potentially be points at any distance on the curve. A more interesting question is how easy can you find two points that are $n$ far away from each other. Formally, given a valid point $P = (x, y)$, the probability of the next $n$ consecutive values for the $x$ coordinate to generate invalid points is $2^{-n}$. – Hulub Aug 19 at 13:52
• @Hulub: do we know that? Is there a proof that the valid $x$ coordinates are not non-uniformly distributed? There might be; I haven't seen such a proof... – poncho Aug 19 at 14:53
• By your argument, that every $x$ value has a probability of $1/2$ to generate a valid point, that also means it has a probability of $1/2$ to generate an INVALID point. If we take 3 consecutive $x$ values, the probability of all 3 to NOT generate valid points is $1/2 * 1/2 * 1/2 = 2^{-3}$. Hence, the generalisation holds. – Hulub Aug 22 at 7:49
• @Hulub: that does not follow. Yes, if we take 3 random $x$ values, the probability is approximately $2^{-3}$ (approximately because the probability of a single value isn't precisely $2^{-1}$). On the other hand, we don't know if the valid $x$ values are clustered; any correlation because whether successive values are valid would invalidate your argument (and as I said previously, I don't know of any proof about correlation of successive $x$ values) – poncho Aug 22 at 16:43