2
$\begingroup$

I hear that there should be a point at infinity on secp256k1. I wounder how to calculate it and what does it even mean. I tried to calculate it as $P_{inf}=P+(-P)$ but this gives different results for different P. Are there more than one point at infinity?

Geometrically thinking on an elliptic curve, adding two points that are symmetric against x-axis, should not be feasible because any vertical line on x-y plane will only intersect the curve at TWO points not THREE.

$\endgroup$
5
$\begingroup$

Yes, there is a point at infinity $O$ on Elliptic Curves (EC). Let the EC be given in Weierstrass equation;

$$y^2 = x^3 +a x + b$$

$O$, the point at infinity can have different values according to the underlying coordinate system;

Coordinate Systems

For an elliptic curve over $\mathbb{F}_p$;

  • In Homogeneous Coordinates (also known as Projective Coordinate), the points are defined as $(x:y:z),z\neq 0$ corresponding to affine point $(\frac{x}{z},\frac{y}{z})$. The point at infinity is $(0:1:0)$ and negative value of $(x:y:z)$ is $(x:-y:z)$
  • In Jacobian Coordinate the points are defined as $(x:y:z),z\neq 0$ corresponding to affine point $(\frac{x}{z^2},\frac{y}{z^3})$. The point at infinity is $(1:1:0)$ and negative value of $(x:y:z)$ is $(x:-y:z)$

Now, what is $O$ in affine coordinates? Try to convert $O$ back into an affine coordinate! Well, we cannot represent it! See this answer Thus, we simply say it is $O$. But, magically, it can be encoded in implementations.

The Group Law

The points on an elliptic curve form an additive group with an identity $O$. For geometrical meaning please see the below image from Wikipedia Elliptic Curves The group law.

Geometric interpretation of addition on a Weierstrass curve

We, however, arithmetically can define the addition rules in affine coordinates as;

Let $P=(x_1,x_2)$ and $Q=(x_2,y_2)$ be two point in the elliptic curve.

  1. $P+O=O+P=P$
  2. If $x_1 = x_2 $ and $y_1 = - y_2$ and $Q =(x_2,y_2)=(x_1,−y_1)=−P$ then $P + (-P) = O$
  3. If $Q \neq -P$ then the addition $P+Q = (x_3,y_3)$ and the coordinate can be calculated by;

\begin{align} x_3 = & \lambda^2 -x_1 - x_2 \mod p\\ y_3 = & \lambda(x_1-x_3) -y_1 \mod p \end{align}

$$ \lambda = \begin{cases} \frac{y_2-y_1}{x_2-x_1}, & \text{if $P \neq Q$} \\[2ex] \frac{3 x_1^2+a}{2y_1}, & \text{if $P = Q$} \\[2ex] \end{cases}$$

For Jacobian Coordinate operations see this link.

$\endgroup$
  • 1
    $\begingroup$ In 2 you mean P + Q = O (or P + -P) $\endgroup$ – dave_thompson_085 Jan 6 at 10:13
  • $\begingroup$ @dave_thompson_085 thanks. corrected. $\endgroup$ – kelalaka Jan 6 at 10:18
  • $\begingroup$ @kelalaka the Wikipedia link you have supplied is saying that if P and Q are opposites of each other, we define $P + Q = O$. Why we cannot conclude $P+(-P)=O$ is always true? By the way what is the random looking output value is that my computer program in python is giving as output? finally is it possible to calculate $O$ so that for any randomly given $P$ the computer program can calculate $P+O=P$? $\endgroup$ – PouJa Jan 6 at 10:57
  • $\begingroup$ The points are forming an additive group with identity $O$ so $P+(-P) = O$. Wikipedia also says the opposite of a point $P$ is $-P$. For the programming part, unfortunately, off-topic here. Please ask a question on StackOverflow. $\endgroup$ – kelalaka Jan 6 at 11:17

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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