Projective Curves

Here, I will fill in some of the gaps (quite literally) from the earlier post on algebraic and elliptic curves. There, I showed how we can, algebraically, construct points on a curve in terms of already known ones. For curves of degree 2, or conics, this led to a parameterisation of the entire curve. For degree 3, or elliptic curves, this gave a binary operator allowing us to construct one new point out of any two existing points which, as I will cover later, leads to the group structure used in the Bitcoin digital signature algorithms. If you have not already, I would suggest reading that post before coming back to this one. However, there was one small problem that we encountered. For some special cases, the construction is not well-defined and directly applying the algebraic formulas would give divide-by-zero errors. We interpreted this as giving points at infinity. However, it was not clear what the points at infinity are, or how they should be handled algebraically. I will state upfront, this post consists of the mathematical background to better understand elliptic curves. If you are happy with the explanation given in the previous post, and to take at face value how to handle the point at infinity of the curve used by Bitcoin, then this post can be skipped. On the other hand, if you want to understand the mathematics better, then read on.

As an example, consider the hyperbola in figure 1 given by the solutions to ${x^2-y^2=1}$ . Most lines that intersect the curve at all, will intersect it at precisely two points. There are tangents to the curve, that will intersect at one point, but with multiplicity two. However, lines which are perpendicular to one of the asymptotes have gradient 1 or -1 and will intersect at most once. To fill in this missing point, we interpret these lines as also intersecting the curve at a point at infinity. All parallel lines intersect at the same point at infinity and, in the case of the hyperbola, the asymptotes themselves (which have gradient 1 or -1 and pass through the origin) are interpreted as intersecting a point at infinity with multiplicity 2.

Next, consider the elliptic curve given by ${y^2=x^3+3}$ as in figure 2. Most lines which intersect this at two points, will also intersect at a third point. The exception is vertical lines, which intersect at exactly two points. We interpret these as also intersecting the point at infinity of the curve, which we denoted by ${\mathcal O}$ . Furthermore, for consistency, we wrote ${\mathcal O\circ\mathcal O=\mathcal O}$ , meaning that the line tangent to ${\mathcal O}$ actually intersects it with multiplicity 3. This line is actually the line at infinity.

What causes these points at infinity to appear? They should not just be ignored, especially for the case of elliptic curves, as that would mess with the nice algebraic properties.

We defined a curve as the set of solutions ${(x,y)}$ to a polynomial equation in two unknowns x and y, which are allowed to take values in a given field F. The set of all points ${(x,y)}$ as x and y take values in F is known as the affine plane, and a curve defined as above is more correctly called an affine curve or affine algebraic curve. The problem is that the affine plane is not complete, and is effectively missing points at infinity. Adding these points leads us to the projective plane. Defining a curve over the projective plane will naturally include the points at infinity, so that they can be handled in exactly the same way as the ‘finite’ points which lie on the affine plane.

Let me start with the projective line over the base field F. This is denoted ${\mathbb P^1(F)}$ , and points on the projective line are written as ${(x:y)}$ for elements x and y of the base field which are not both zero. We also identify points if they are scaled by a nonzero element of the field, so that ${(x:y)=(ax:ay)}$ for any nonzero a in F. Expressed slightly differently, ${(x_1:y_1)}$ and ${(x_2:y_2)}$ represent the same projective point if and only if ${x_1y_2=x_2y_1}$ . In the case where ${y_1\not=0}$ , then this means that ${y_2\not=0}$ and ${x_1/y_1=x_2/y_2}$ . So, these points can be thought as ratios, equal to ${x/y}$ , which are just elements of the base field. This is expressed by the map ${x\rightarrow(x,1)}$ from the base field to the projective line, which has inverse ${(x:y)\rightarrow x/y}$ over ${y\not=0}$ . However, we also include the point with ${y=0}$ , which is the point at infinity.

There is the obvious symmetry on the projective given by exchanging the components, so that ${(x:y)}$ goes to ${(y:x)}$ . Using the identification of points on the projective line with the base field, this is just the multiplicative inverse for nonzero x

$\displaystyle x\rightarrow (x:1)\rightarrow(1:x)=(1/x:1)\rightarrow 1/x.$

Also, 0 and the point at infinity are exchanged. Under this map, a polynomial of the form ${p(x)=c_0+c_1x+c_2x^2+\cdots}$ is taken to ${p(x^{-1})=c_0+c_1x^{-1}+c_2x^{-2}+\cdots}$ , which is not a polynomial. However, rational functions (i.e., the ratio of two polynomials) does remain a rational function under the transformation, suggesting that polynomials are not natural objects defined on the projective line, but rational functions are.

Note that a line in the affine plane through a fixed point P can be parameterised by ${P+t(u,v)}$ , for elements ${u,v}$ of the base field which are not both zero. Then, another line ${P+t(u^\prime,v^\prime)}$ is in fact the same line if ${(u^\prime,v^\prime)}$ is proportional to ${(u,v)}$ . This shows that the points in the projective line are in one-to-one correspondence with the lines in the plane through P. Under this correspondence, the line ${P+t(u,v)}$ is associated with the point ${(u:v)}$ . Furthermore, as described in the previous post, the points of the projective line over the real numbers are in one-to-one correspondence with the unit circle. This is as in figure 3, showing the mapping between the lines through point P, the points of a circle, and the base field F together with the point at infinity.

The projective plane over the base field F, denoted by ${\mathbb P^2(F)}$ , can be constructed in a similar way. Individual points are expressed as ${(x:y:z)}$ for elements x,y,z of the base field which are not all zero. Points are identified if they are equal up to a scaling factor, ${(x:y:z)=(ax:ay:az)}$ for a nonzero a in F. Alternatively, fixing a point P in the affine plane, we can identify a point ${(u:v:w)}$ in the projective plane with the line ${P+t(u,v,w)}$ through P.

Note that, by scaling, points ${(x:y:z)}$ in the projective plane can be assumed to have ${z=1}$ or ${z=0}$ . The points with ${z=1}$ are in one-to-one correspondence with points ${(x,y)}$ in the affine plane. The points with ${z=0}$ are still only defined up to a scaling factor, so are in correspondence with points ${(x:y)}$ in the projective line,

$\displaystyle \begin{aligned} &F^2\rightarrow \mathbb P^2(F),\ \ (x,y)\mapsto(x:y:1),\\ &\mathbb P^1(F)\rightarrow\mathbb P^2(F),\ \ (x:y)\mapsto(x:y:0). \end{aligned}$

This identifies the projective plane as the disjoint union of the affine plane and the projective ‘line at infinity’.

For the field of real numbers, any point ${(x:y:z)}$ in the projective plane can be scaled so that ${x^2+y^2+z^2}$ is equal to one. As multiplying through by ${-1}$ leaves the point unchanged, this identifies points on the projective plane with pairs of antipodal points on the unit sphere. The north hemisphere is in one-to-one correspondence with the affine plane (as is the south hemisphere, identifying antipodal points), with the equator at ${z=0}$ corresponding to the projective line at infinity, This is as in figure 4.

Clearly, n-dimensional projective space can be defined in the exact same way, as points ${(x_0:x_1:\cdots:x_n)}$ for elements ${x_i}$ of the base field, not all zero, where we identify points which are equal up to a scaling factor. Here, though, I am only looking at the projective line and plane.

Linear Equations

The equation for a line for points ${(x:y:z)}$ in the projective plane is

$\displaystyle ax+by+cz=0,$

(1)

where a,b,c are constants in the base field, not all equal to zero. Note that each of the terms is a multiple of one of the coordinates x,y,z. There is no constant term independent of these since, points in projective space are invariant under scaling, so the same must also be true for the equation of a line. Multiplying each of x,y,z through by a scaling factor also scales the left hand side of (1) by the same factor, so does not effect whether or not it is equal to zero. This would not be the case if a constant term was included. Note also, that for points ${(x:y:1)}$ corresponding to the affine plane, (1) is just the usual equation for a line ${ax+by+c=0}$ , so long as a and b are not both zero. On the other hand, if a and b are both zero, then the equation gives the points ${(x:y:0)}$ , which is the line at infinity.

As for the affine line, so long as a is nonzero, given any values of y,z we can solve (1) simply as

$\displaystyle x=\frac{by+cz}{-a}.$

This provides a one-to-one map from points ${(y:z)}$ of the projective line to points ${(x:y:z)}$ in the projective plane solving (1). Similarly, if b or c is non-zero, the same idea holds with the roles of x and y or z exchanged.

More generally, for any two distinct points ${P=(u:v:w)}$ and ${Q=(u^\prime:v^\prime:w^\prime)}$ then the unique line passing through these can be parameterised as

$\displaystyle P_{s,t}\equiv sP+tQ\equiv(su+tu^\prime:sv+tv^\prime:sw+tw^\prime)$

(2)

for points ${(s:t)}$ in the projective line. There is a slight abuse of notation here, since the left hand side of (2) is only defined in terms of the choice of representation of the points P and Q. Scaling them by nonzero constants changes the parameterization, but does not affect the line through P and Q.

It is a straightforward result that any two lines in the projective plane intersect. Using (1) for the equation of a line, we obtain two linear equations in three unknowns for the point of intersection, which always has a nontrivial solution. Furthermore, two distinct lines will intersect at a unique point.

Just as for the affine plane, the lines through a fixed point P are in one-to-one correspondence with points ${(u:v)}$ on the projective line. For example, consider a point ${P=(x:y:1)}$ not at infinity. The affine lines though this point are just ${(x,y)+t(u,v)}$ for points ${(u:v)}$ in ${\mathbb P^1(F)}$ . In the projective plane, this corresponds to the line (2) passing through P and the point ${Q=(u:v:0)}$ at infinity. More generally, for any line L in the projective plane not containing P, (2) gives a one-to-one map between the points Q on L and the lines through P.

Quadratic Equations

I now look at higher order algebraic curves. Recall that a curve for points ${(x,y)}$ in the affine plane is determined by the zeros of a polynomial ${p(x,y)}$ of some degree d. As the points ${(x:y:z)}$ of the projective plane, with z nonzero, correspond to ${(x/z,y/z)}$ in the affine plane, the equation defining the curve becomes ${p(x/z,y/z)=0}$ . Since this involves dividing by z, it is not defined at the line at infinity, where ${z=0}$ . This is easily remedied by multiplying through by ${z^d}$ , giving a polynomial of degree d in x,y,z. For example, consider a general degree 2 (quadratic) polynomial,

$\displaystyle p(x,y)=ax^2+bxy+cy^2+dx+ey+f.$

We convert to a polynomial in x,y,z,

$\displaystyle \begin{aligned} p(x,y,z)&= p(x/z,y/z)z^2\\ &=ax^2+bxy+cy^2+dxz+eyz+fz^2. \end{aligned}$

The result is a homogeneous polynomial in x,y,z. By this, we mean each of the monomial terms in the polynomial expansion has the same degree ${d=2}$ . A consequence is that scaling ${x,y,z}$ by a constant ${\lambda}$ has the effect of scaling ${p(x,y,z)}$ by ${\lambda^d}$ , meaning that it does not affect whether or not it evaluates to zero. So, the equation ${p(x,y,z)=0}$ is a well-defined statement for points ${(x:y:z)}$ in the projective plane.

For example, the hyperbola ${x^2-y^2=1}$ in the affine plane extends to the projective curve ${x^2-y^2=z^2}$ for points ${(x:y:z)}$ in the projective plane. This is shown in figure 5. The apparently two distinct components of the hyperbola over the real numbers are really just a single closed curve in the projective plane passing through the line at infinity at two points. This shows as two circles in the sphere representation but, as we identify antipodal points, it is really just a single circle.

This is the general idea, a projective curve of degree d consists of the ponts ${(x:y:z)}$ in the projective plane satisfying ${p(x,y,z)=0}$ for a homogeneous degree d polynomial p. We assume that p is irreducible, so that it does not factor as a product of polynomials of lower degree (if it did, the curve would be a union of curves of lower degree). A point on the curve will be said to be singular if the partial derivatives ${p_x,p_y,p_z}$ also all vanish there.

Consider a quadratic curve (or conic) of the form ${p(x,y,z)=0}$ for p homogeneous of degree 2, as in (1). Suppose that we know one nonsingular point P on the curve. Then, for any line though this, parameterized as ${P_{s,t}=(x:y:z)}$ as in (2), ${p(x,y,z)}$ is a homogeneous degree 2 polynomial in s,t vanishing when t is zero,

$\displaystyle p(x,y,z)=t(\lambda s+\mu t).$

The terms ${\lambda,\mu}$ cannot both be zero, otherwise p would vanish on the entire line, which can only be the case if it has a linear factor. Since we assume that it is irreducible, this is not the case. So, the line through P intersects at the second point ${P_{s,t}}$ corresponding to ${(s:t)=(-\mu:\lambda)}$ . This provides a one-to-one parameterisation of the points on the conic in terms of the lines through P.

Looking at the circle example ${x^2+y^2=1}$ as in the previous post, in projective space this becomes ${x^2+y^2=z^2}$ . Then, fix the point ${P=(1:0:1)}$ . The line though P and the point ${(-u:v:0)}$ at infinity is parameterised as ${(s-tu:tv:s)}$ . This passes through the circle at,

$\displaystyle (s-tu)^2+(tv)^2-s^2=t(tu^2+tv^2-2su).$

So, we have the solution ${(s:t)=(u^2+v^2:2u)}$ , parameterising the points of the circle as,

$\displaystyle \left(v^2-u^2:2uv:u^2+v^2\right).$

Using the real numbers as the base field, ${u^2+v^2}$ will be nonzero, so we can divide through by this to get the same parameterization as found in the previous post. For the complex numbers, or any base field containing a square root ${i}$ of -1, there will be one point with ${u=i}$ and ${v=1}$ which maps to the point at infinity ${(1:i:0)}$ on the conic.

Cubic Equations

Now consider a polynomial ${p(x,y,z)}$ which is homogeneous of degree 3, and the algebraic curve ${p(x,y,z)=0}$ . We suppose that p is irreducible and does not contain singular points. This is an elliptic curve. For example, the Weierstrass normal form mentioned in the previous post for affine elliptic curves is,

$\displaystyle y^2=x^3+ax+b.$

In projective space, this becomes the homogeneous third order polynomial equation

$\displaystyle y^2z=x^3+axz^2+bz^3$

for points ${(x:y:z)}$ in projective space, corresponding to the polynomial

$\displaystyle p(x,y,z)=y^2z-x^3-axz^2-bz^3.$

Evaluated on the line at infinity ${(x:y:0)}$ , we obtain ${p(x,y,0)=-x^3}$ , giving a single point of intersection at ${(0:1:0)}$ with multiplicity 3. This is as in figure 6 below. The elliptic curve ${y^2=x^3+1/2}$ in the real projective plane, represented as points on the sphere, becomes a closed curve intersecting the equator tangentially at a single pair of antipodal points.

Now, consider two points P and Q on the degree 3 curve. They are joined by the line ${P_{s,t}=(x:y:z)}$ as in (2) and, evaluating p along this line gives a homogeneous degree polynomial, which must vanish at the points P and Q corresponding to ${s=0}$ and ${t=0}$ ,

$\displaystyle p(x,y,z)=st(\lambda s+\mu t).$

This cannot vanish identically, otherwise the elliptic curve would contain the line, and have a linear factor. So, ${\lambda}$ and ${\mu}$ are nonzero, giving a third point of intersection corresponding to ${(s:t)=(-\mu:\lambda)}$ . Hence, the point ${R=P\circ Q}$ is uniquely defined. In a similar way, if ${P=Q}$ (and is nonsingular), then we take ${P_{s,t}}$ to be tangent to the curve at P, in which case ${p(x,y,z)}$ vanishes with multiplicity 2 at ${t=0}$ giving,

$\displaystyle p(x,y,z)=t^2(\lambda s+\mu t).$

Again, we have a uniquely determined third point of intersection at ${(s:t)=(-\mu:\lambda)}$ . So, ${P\circ Q}$ is defined everywhere, and may or may not correspond to a point at infinity.

We already noted that an elliptic curve in Weierstrass form has a unique point ${\mathcal O=(0:1:0)}$ at infinity. As the line at infinity intersects this point with multiplicity 3, we have already determined the identity ${\mathcal O\circ\mathcal O=\mathcal O}$ . Given points ${P=(x:y:1)}$ and ${Q=(x:-y:1)}$ on the elliptic curve, then ${P,Q,\mathcal O}$ all lie on the horizontal line ${(sx:sy+t:s)}$ , so that ${P\circ Q=\mathcal O}$ , and ${P\circ\mathcal O=Q}$ . There is no need recompute the explicit formulas not involving the point at infinity, as the calculation from the previous post applies in the same way.

This all works out as was stated in the previous post, but using projective space explains why the point at infinity behaves as it does, and allows for different parameterizations which may have different points at infinity.

	coinbase transaction… on Merge Mining and Auxiliary Pro…
	coinbase transaction… on Merge Mining and Auxiliary Pro…
	coinbase transaction… on Merge Mining and Auxiliary Pro…
	coinbase transaction… on Merge Mining and Auxiliary Pro…
	coinbase transaction… on Merge Mining and Auxiliary Pro…
	Cleta Yates-Florez on Group Theory
	Non-Interactive Proo… on Zero Knowledge Proofs
	George Lowther on Welcome!