5
$\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$
3
  • 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, 2015 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$ Jan 19, 2015 at 9:31
  • $\begingroup$ @user13741 The point certaily exists, but it is not on the curve. ;) $\endgroup$
    – fkraiem
    Dec 17, 2015 at 7:52

2 Answers 2

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$
2
  • 1
    $\begingroup$ Need more explanation in your answer for me to give it a +1. $\endgroup$
    – mikeazo
    Jan 20, 2015 at 15:49
  • $\begingroup$ @mikeazo My answer is updated. $\endgroup$
    – Nayef
    Feb 4, 2015 at 8:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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