In elliptic curve, what does the point at infinity look like?

Question

We know that for each point $P$ on curve $E$ there exists a minimum scalar $k$ such that $kP$ equals the point at infinity. And the book Cryptography Theory and Practice by Douglas R. Stinson only mentions that adding $P_1=(x,y)$ and $P_2=(x,-y)$ equals point at infinity $O$. But in terms of coordinates, how does the point at infinity look like?

The point at infinity is said to give $P+O=P$, but that is not evident from the book/tutorial. As an example, consider the curve $y^2=x^3+x +6$ mod 11 (this appears on slide 15 of this pdf and also on pages 185-186 of the aforementioned book). Taking $P=(2, 7)$ as the basis point, one generates all the points in $E$ up to point $(2, 4)$.

Now, $(2, 7)+(2, 4)$ is the so-called "point at infinity" $0$. But it is just unclear

1. how $0+(2, 7)=(2, 7)$, and
2. how $(2, 7)+(2, 4)$ should be visualized so that adding $(2, 7)$ again takes us back to $(2, 7)$.

Same slide (#15) also includes an example with curve $y^2=x^3+2x+3$ mod 5. Scalar multiplication on $P=(1, 1)$ "generates" all the points listed there except $(4, 0)$. How does one actually get to $(4, 0)$? I tried other "starting points" (e.g., $(3, 1)$) but to no avail.

Answer 1

A good way to think of the point at infinity is that it is an artificial point of the curve, introduced to fill gaps in the table for addition of points on the curve, and act as the group's neutral element. That

• Makes point addition an internal law (addition of two points on the curve becomes a point on the curve, with no exception). Otherwise, there would be gaps. For example, on the curve $y^2\equiv x^3+x+6\bmod11$ we would have no value for $(2,4)+(2,7)$. To fill that gap, we define that expression to yield the point at infinity.
• Ensures we have a neutral, which is required for a group. That is, some $N$ so that for all point $P$ on the curve, $P+N=N+P=P$.

We name that artificial curve element the "point at infinity", rather than zero or the neutral, because on a continuous elliptic curve, when $P'$ on the curve gets close to $P$ on the curve, the sum $P+(-P')$ obtained by geometric construction goes away from the origin, so that the neutral ends up "at infinity". On discrete curves, the name is just kept.

---

1. how $0+(2, 7)=(2, 7)$

It holds by definition of neutral $0$.

2. how $(2, 7)+(2, 4)$ should be visualized so that adding $(2, 7)$ again takes us back to $(2, 7)$.

It holds because we define $(2,7)+(2,4)$ as the neutral: $$\begin{align}\big((2,7)+(2,4)\big)+(2,7)&=0+(2,7)\quad \quad \quad \quad \quad \quad \\&=(2,7)\end{align}$$

An alternative justification is commutativity and associativity, combined with the addition law for normal curve points: $$\begin{align}\big((2,7)+(2,4)\big)+(2,7)&=\big((2,4)+(2,7)\big)+(2,7)\\&=(2,4)+\big((2,7)+(2,7)\big)\\&=(2,4)+(5,2)\\&=(2,7)\end{align}$$

---

For affine coordinates and an elliptic curve in Weierstrass form (as in the above example), there is no natural representation of the point at infinity that would match the equation. Hence arithmetic involving that special point will need a special case. Common conventions are $x=0$, or $x=y=0$, because these are slightly faster to test and assign on many architectures.

Answer 2

You can think of the point at infinity as an extra point kludged into the set to make the curve work out as a group, but that's a little unsatisfying: in the geometric picture of a curve there's no place for the point at infinity, and in the algebraic construction the point at infinity is this weird magic object $\mathcal O$ with no coordinates.

$$E := \{ (x, y) \in k^2 \mid y^2 = x^3 - x + 1 \} \cup \{\mathcal O\}$$

Instead, it is better to think of things in projective coordinates: $$E := \{ (X : Y : Z) \in \mathbb P^2(k) \mid Y^2 Z = X^3 - X Z^2 + Z^3 \}.$$ Here the notation $(X : Y : Z)$ means the set of all triples $(\lambda X, \lambda Y, \lambda Z)$ for some $\lambda \in k$, or equivalently the line in the three-dimensional space $k^3$ that passes through the origin $(0, 0, 0)$ and the point $(X, Y, Z)$, provided at least one of $X$, $Y$, or $Z$ is nonzero. Notice that I didn't write $\cdots \cup \{\mathcal O\}$: as it happens, there is a natural set of projective coordinates for the point at infinity, namely $(0 : 1 : 0)$ (or $(0 : 2 : 0)$, or $(0 : 128364/2486 : 0)$, etc.).

Not only is there a natural set of projective coordinates, but there is a geometric picture too. If we paste the picture above on the plane $z = 1$, we are taking the intersection of all the projective lines $(X : Y : Z)$ satisfying $Y^2 Z = X^3 - X Z^2 + Z^3$ with the affine points $(x, y)$ satisfying $y^2 = x^3 - x + 1$ pasted on the plane $z = 1$—all except for one such projective line:

The one exception is the $y$ axis, $(0 : 1 : 0)$, which is exactly the point at infinity! If you draw lines from the origin to the affine curve pasted on the plane $z = 1$, that is if you map $(x, y) \mapsto (x : y : 1)$, as you get further and further out the wings of the curve, the line gets closer and closer to the $y$ axis—along both wings! In the limit toward infinity, which has no affine coordinates, you just get the $y$ axis $x = z = 0$. For every other point, affine coordinates can be computed by $(X : Y : Z) \mapsto (X/Z, Y/Z)$.

So while it doesn't show up in the affine picture, the point at infinity has a natural geometric and algebraic interpretation in projective coordinates of lines through the origin.

---

Appendix A: Asymptote code for affine elliptic curve plot

import graph;

size(5cm, 0);

pair O = (0,0);
pair X = (1,0);
pair Y = (0,1);

// y = F(x) = sqrt(f(x))
real f(real x) { return x^3 - x + 1; }
real df(real x) { return 3*x^2 - 1; }
real F(real x) { return sqrt(max(0, f(x))); }

draw(-2X -- 2X, arrow=Arrows(TeXHead), p=gray(2/3) + dashed,
  L=Label("$x$", position=EndPoint, align=S));
draw(-3Y -- 3Y, arrow=Arrows(TeXHead), p=gray(2/3) + dashed,
  L=Label("$y$", position=EndPoint, align=E));

real lo = newton(f, df, -1);
real hi = 2;

guide g = graph(F, lo, hi, Hermite);
draw(g, arrow=Arrow(TeXHead));
draw(reflect(O, X)*g, arrow=Arrow(TeXHead));

---

Appendix B: Asymptote code for projective elliptic curve plot

import graph;
import three;

size(10cm, 0);
currentprojection = perspective(4, -8, 4);

// y = F(x) = sqrt(f(x))
real f(real x) { return x^3 - x + 1; }
real df(real x) { return 3*x^2 - 1; }
real F(real x) { return sqrt(max(0, f(x))); }

draw(-Z -- 2Z, arrow=Arrows3(TeXHead2), p=black + dashed,
  L=Label("$z$", position=EndPoint, align=N));
draw(-2X -- 2X, arrow=Arrows3(TeXHead2), p=black + dashed,
  L=Label("$x$", position=EndPoint, align=E));
draw(-3Y -- 3Y, arrow=Arrows3(TeXHead2, arrowheadpen=emissive(red)),
  p=red + dashed,
  L=Label("$y$", position=BeginPoint, align=W));

dot(O);
draw(shift(Z)*scale3(0.1)*unitdisk, surfacepen=emissive(gray(2/3)));

real lo = newton(f, df, -1);
real hi = 1.8;

// Draw the curve on the z=1 plane.

guide gp = graph(F, lo, hi, Hermite);

draw(shift(Z)*shift(-2X)*shift(-3Y)*plane(4X, 6Y), p=gray(2/3));
draw(shift(Z)*(-2X -- 2X),
  arrow=Arrows3(TeXHead2(Z), arrowheadpen=emissive(gray(2/3))),
  p=gray(2/3) + dashed);
draw(shift(Z)*(-3Y -- 3Y),
  arrow=Arrows3(TeXHead2(Z), arrowheadpen=emissive(gray(2/3))),
  p=gray(2/3) + dashed);

draw(shift(Z)*path3(gp), arrow=Arrow3(TeXHead2(Z)));
draw(shift(Z)*path3(reflect((0,0),(1,0))*gp), arrow=Arrow3(TeXHead2(Z)));

draw(unitsphere,
  surfacepen=material(white + opacity(0.5), ambientpen=white));

// Draw the curve on the surface of the sphere.

guide3 gs;

int nsamples = 400;

// Sample with linear spacing for the first part of the curve.
for (int i = 0; i < nsamples; ++i) {
  real x = lo + ((hi - lo)*(i/nsamples));
  real y = F(x);
  gs = gs -- unit((x, y, 1));
}

// Then sample with exponential spacing for the rest.
for (int i = 0; i < nsamples; ++i) {
  real x = hi + (exp(200*(i/nsamples)) - 1)/100;
  real y = F(x);
  gs = gs -- unit((x, y, 1));
}

// Oughta converge to the Y axis.
gs = gs -- Y;

// Draw all four copies of the same shape.
draw(gs);
draw(reflect(O,X,Z)*gs);
draw(reflect(O,X,Y)*reflect(O,Y,Z)*gs);
draw(reflect(O,X,Y)*reflect(O,Y,Z)*reflect(O,X,Z)*gs);

// Draw some sample points in projective space on the curve.

void
showpoint(real x, pen p=blue)
{
  real y = F(x);
  triple P = (x, y, 1);
  draw(-P--1.5P, arrow=Arrows3(TeXHead2, arrowheadpen=emissive(p)), p=p);
  dot(P, p=p);
  dot(unit(P), p=p);
  dot(unit(-P), p=p);
}

showpoint(lo + 0.3);
showpoint(lo + 1.0);
showpoint(lo + 2.0);
showpoint(lo + 2.8);

// Axis line already shown; add a dot.

dot(Y, p=red);
dot(-Y, p=red);