4
$\begingroup$

For Bitcoin's ECDSA curve (secp256k1, where $a=0$, $b=7$), why can't the generator point's first coordinate be $x=0$? That is, the point on the curve would be $(0,y)$ where $y$ satisfies $y^2 = 0^3 + 7=7$.

Are there any elements other than $0$ which can't be used as a generator point's $x$ coordinate?

$\endgroup$
  • 1
    $\begingroup$ That point doesn't exist. For the prime modulus used by secp256k1, 7 is a quadratic non-residue, meaning y^2 = 7 has no solution. $\endgroup$ – user13741 Jan 19 '15 at 6:09
  • 1
    $\begingroup$ For an elliptic curve, about half the x values have two associated points, the other half of the x values has none (they correspond to the twist of the curve). $\endgroup$ – CodesInChaos Jan 19 '15 at 9:31
  • $\begingroup$ @user13741 The point certaily exists, but it is not on the curve. ;) $\endgroup$ – fkraiem Dec 17 '15 at 7:52
5
$\begingroup$

Here is a plot of secp256k1 over the reals. That I'll use for illustration purposes.

enter image description here

What happens at $x=-3$, well, we get $y^2 = (-3)^3+7$ which reduces to $y^2=-20$. Solving for $y$ we get $y=\sqrt{-20}$, which is not in the reals, so, we cannot have a point on that curve for $x=-3$.

This is what is happening. In the case of the real secp256k1 used in bitcoin, we are using a finite field instead of the reals. In the reals, the equation $y^2=x^3+7$ is not defined for the entire domain. Similarly, over the finite field, the equation is not defined over the entire field.

In other words, in order for there to be a point (actually 2 points) on the curve at $x$, we must be able to take the square root of $x^3+7$ in the field. As to the number of valid $x$ values, see this question on Math.SE.

$\endgroup$
1
$\begingroup$

The point simply is not on the curve!

Update:

The curve secp256k1 has no point such that the x-coordinate is 0. There is no integer which its square is 7 modulo FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFC2F.

I hope this helps to understand why there is no such a point.

$\endgroup$
  • 1
    $\begingroup$ Need more explanation in your answer for me to give it a +1. $\endgroup$ – mikeazo Jan 20 '15 at 15:49
  • $\begingroup$ @mikeazo My answer is updated. $\endgroup$ – Nayef Feb 4 '15 at 8:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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