In Elliptic Curve, what does the point at infinity look like? We know that for each point $P$ in curve $E$ there exists a minimum scalar $k$ such that $k*P$ equals the point at infinity. And the book Cryptography Theory and Practice by Douglas R. Stinson only mentions that adding $P1=(x,y)$ and $P2=(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 


how $0+(2, 7)=(2, 7)$, and
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.
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 &lt; 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 &lt; 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);