Bitcoin and other cryptocurrencies make use of cryptographic techniques employing elliptic curves, such as in the digital signature algorithms. Most of the time we just make use of these methods, treating them as ‘black box’ algorithms, and do not worry too much about what is going on under the hood. If you do decide to look up descriptions of them, including the Wikipedia entries for ECDSA and Schnorr signatures, or the entry in Bitcoin Wiki, then you will be confronted with some rather abstract group algebra. Then, you might learn that the group used by Bitcoin is the secp256k1 elliptic curve described by the equation y2 = x3 + 7 over the field of integers modulo some huge prime. Digging further, the group operation is given by some point multiplication formulas. By this time, if you did not really understand what was going on to start with, it can begin to look like some kind of black magic.
In this post, I will explain the underlying mathematical ideas. The hope is to demystify the algorithms but, to be clear at the outset, it will involve quite a bit of algebra. If you are not already proficient at such algebraic methods, then it will require some time to build up a good understanding.
Elliptic curves, as used by Bitcoin, are special examples of algebraic curves. These are curves in the plane described by the points (x,y) solving a polynomial equation. For example, a circle of radius r is described by the equation x2 + y2 = r2 and a parabola is described by y = x2. There is an endless list of formulas that we could pick, but a slightly more complicated example is
| y2 + 3xy – x3 + 4x = 1. | (1) |
Figure 1 shows the set of points in the plane solving this equation. There are also online equation graphers that you can use to play about with different polynomial expressions.
Such algebraic formulas come up a lot in mathematics. Formulas in a single variable x include quadratics such as x2 – 3x + 1 = 0, which are widely studied at high school level where the aim is to solve for the unknown x. In algebraic curves, we have two unknowns x and y, with the implication that there will usually be (infinitely) many solutions. As it is not possible to list them all in one go, the aim is to find an algebraic method of generating them.
Any polynomial expression in unknowns x and y is a linear combination of monomials, which are just products of nonnegative integer powers of the variables. A monomial of the form xrys has degree r + s, and the degree of a polynomial is just the maximum of the degrees of its monomial terms. For example, the equation of a circle x2 + y2 = r2 has degree 2, and equation (1) above has degree 3. Generally speaking, polynomial expressions become harder to handle as the degree increases. Degree 2 or less can be described completely with straightforward methods, and degree 4 or greater can be intractable. The sweet spot, of degree 3, is simple enough to enable various algebraic constructions of solutions to the equation but, on the other hand, is not so straightforward as to be uninteresting. These degree 3 curves are called elliptic curves, as are used in digital signature algorithms.
Rather than jumping straight into the arithmetic of elliptic curves, I will start a bit more gradually to try and get a better understanding of how we can algebraically construct points on them. The more advanced and implementation specific details required for elliptic curve cryptography methods will be left until a later post. To warm up, I look at degree one and two, showing how we can parameterize the set of solutions by some straightforward constructions. Then, I move on to degree 3, or elliptic curves. Similar ideas can be used as with lower degrees, but they do not lead to a complete parameterization. Instead, they only allow us to construct new solutions from known cases, one by one, gradually building up a (potentially infinite) set of solutions. It is this method of constructing new solutions from existing ones that gives elliptic curves their group structure used in cryptography, although I will leave the group theory until a later post.
The Base Field
First, before solving an equation, we need to know in what space the unknowns x and y lie. Often, this will be the space of real numbers, so that (x, y) represent points in the plane and the collection of all such points will form smooth curves. For example, the curve of equation (1) was plotted in figure 1 above. This example demonstrates that an algebraic curve, when plotted over the real numbers, can actually break into a collection of disconnected components, each of which can be closed and bounded, or open and extend out to infinity. Such plots can help guide our intuition and understand the constructions involved although, in practice, we often do not want to restrict to solutions in the real numbers.
In general, we consider such algebraic equations over a base field, which I will denote by F. That is, x and y can take values in F so, in the description above, F will be the set of real numbers. Often, instead, we consider solutions lying in the following fields,
- The rational numbers ℚ.
- The real numbers ℝ.
- The complex numbers ℂ.
Number theory is concerned mainly with the rational numbers, whereas analysis is concerned with the real numbers or, enlarging the possible solution set, the complex numbers. From the point of view of writing a computer algorithm to exactly describe solutions, these fields all have a major drawback. They are infinite. So, in any fixed amount of space and with a fixed amount of calculation time available, it is possible for solutions to grow too large to handle.
The only operations that we need to be able to perform on the base field for the techniques that I will describe are addition, subtraction, multiplication, and division. That is, the usual field operations. Luckily, there are also finite fields that can be used instead. For any prime number p, there is a finite field with exactly p elements. This is the integers modulo p, which we can write as Fp, ℤp or ℤ/(p). The idea is that the elements of this field are represented by integers, but two integers represent the same field element if and only if they are equal modulo p, meaning that they have the same remainder on division by p or, equivalently, that their difference is a multiple of p. If we use [x] to denote the value in Fp represented by an integer x modulo p, then [x] and [y] are equal if and only x – y is a multiple of p. As every integer on division by p has a remainder between 0 and p – 1, all elements of Fp can be represented by an integer in this range. For example, for the smallest prime p = 2, the value of an integer modulo p just depends on whether it is odd or even. For the opposite extreme, the Bitcoin digital signature algorithm uses the huge 256 bit prime number
| p = 2256 – 232 – 29 – 28 – 27 – 26 – 24 – 1. | (2) |
This gives a huge number of elements of the field Fp, but they can all be represented by 256 bit binary numbers.
Addition and multiplication in Fp is given by the integer addition and multiplication, we just need to remember to take the modulo p representation of the result,
| [x][y] = [xy], [x] + [y] = [x + y]. |
All of the algebraic identities which hold in the integers, such as x(y + z) = xy + xz, follow straight across to Fp. There is also a zero element, [0], satisfying [0] + [x] = [x], although it is common to just write 0 in place of [0] for simplicity. Similarly, the negative of [x] is given by [-x] and satisfies the identity [-x] + [x] = 0, but we would usually write -[x] in place of [-x]. When writing an algebraic expression in Fp, it is common notation to just write it over the integers and state that it is intended to be taken modulo p, often by simply writing ‘mod p’ in parentheses. So, [x]2 – [y] = [1] would be written as x2 – y = 1 (mod p).
The only field operation which is not obvious in Fp is division. Given integer x which is not a multiple of p then, in fact, it is possible to find an integer y such that xy = 1 (mod p). This means that [y] is the reciprocal or multiplicative inverse of [x] in Fp, and dividing by [x] is the same as multiplying by [y]. Given an integer z then we just write z/x (mod p) or x-1z (mod p) to mean [zy]. To see that such a multiplicative inverse exists, consider multiplying all of the elements of Fp by x. If two values y1 and y2 have the same value when multiplied by x, modulo p, then x(y1 – y2) will be a multiple of p. As p is prime and does not divide x, this means that it divides y1 – y2, so [y1] = [y2] are the same element of Fp. As Fp has size p, and multiplying by x is one-to-one, the set of multiples of x must also be of size p and, hence, is all of Fp. In particular, [1] is a multiple of [x] or, equivalently, [xy] = [1] for some integer y. This argument is the only place so far that the requirement for p to be prime has been used. In fact, it is the only reason that primality is required, so that we can do division in Fp, making it into a field. A fast and practical method of performing division in Fp when the prime p is very big is provided by the Euclidean algorithm.
There are also fields of size pr for any prime number p and positive whole number power r, known as Galois fields, which are often used in cryptography. The case with exponent r = 1 is just the modular arithmetic described above, and is what is used by Bitcoin.
The general techniques used for algebraic curves that I describe below work in any field, so we not restrict to a specific case. You can think in terms of real numbers, or rational numbers, if you like and then when applying the ideas, can substitute this by whatever field is required.
Linear Equations
To start the warm-up exercise, consider a polynomial of degree 1 in the unknowns x, y,
| p(x, y) = ax + by + c |
where a, b and c are constant coefficients with a and b both non-zero. We want to solve for p(x, y) = 0, which is easy! Supposing that a is not equal to zero, then for any value of y we can set
| x = |
by + c
–a
|
, |
so that (x, y) is on the curve given by p. The corresponding formula with a, x and b, y exchanged holds in the case that b is nonzero. Once we have chosen any point P on the line, then it is parameterized by
| P + t(-b, a) |
as t ranges over the field F. So, points on a line are in one-to-one correspondence with the elements of the field. Alternatively, given any two points P and Q, then
| (1 – t)P + tQ = P + t(Q – P) |
parameterizes the unique line passing through both P and Q.
Quadratic Equations
Let’s step up one degree and look at second order polynomials of the form
| p(x, y) = ax2 + bxy + cy2 + dx + ey + f |
for constant coefficients a,b,c,d,e,f with a,b,c not all zero. This describes a conic section which, depending on the values of a,b,c, can be a hyperbola, a parabola, a circle, or an ellipse.
There may or may not be solutions to the algebraic equation p(x, y) = 0 in the base field. For example, over the real numbers, x2 + y2 – 1 = 0 describes a unit circle, whereas x2 + y2 + 1 = 0 has no solutions. I will assume that we have found one point P = (x1, y1) on the curve and, starting from this, will find all other points. The idea is to take a line
| P + t(u, v) | (3) |
passing through P and in direction (u, v), where u and v are constants not both equal to zero. Other than some exceptional cases, this should intersect the conic at two points, one of which we already know is P, giving us one other point on the curve. Furthermore, since there exists a line joining any two points of the plane, every point of the conic section can be obtained in this way.
Write out the formula for the intersection of the line and the curve,
| p(x1 + tu, y1 + tv) = 0. |
As p is second order, this gives us at most a second order (i.e., quadratic) equation in t. We already know that t = 0 is one root of this quadratic, since P = (x1, y1) was chosen on the curve. Hence, we can factor to get the second solution
| p(x1 + tu, y1 + tv) = (λt + μ)t = 0. | (4) |
where λ, μ are constant coefficients. This has a second solution so long as λ is nonzero, given by t = –μ/λ, and we have obtained the point
| Q = (x1 + tu, y1 + tv). |
So, to summarize. We start with a point P on the curve. Then, for every line through this point, we can solve algebraically for the second point of intersection Q, parameterizing the points of the conic by the lines through P. Note that the line defined by (3) is unchanged if the direction (u, v) is scaled. That is, multiplying by a nonzero constant has the same effect as multiplying t by the same constant, so only changes the parameterization of the line, but does not change the intersection point Q. If v ≠ 0 then we can always scale so that v = 1, in which case the line is defined by (u, 1). For v = 0, we have the vertical line through P. This is a parameterization of the projective line consisting of points (u, 1) over u in the field F, together with the point at infinity (1, 0).
As an example, let’s find all points lying on the unit circle x2 + y2 = 1. The first step is to find one solution and, luckily, there is the very simple one given by x1 = 1 and y1 = 0. So, take P = (1, 0). Next, consider a line through this point in direction (-u, v),
| (x, y) = (1 – tu, tv). |
Here, I flipped the sign of u just to avoid a minus sign in the solution, but this is not important. The equation p(x, y) = 0 becomes,
| x2 + y2 | = (1 – tu)2 + (tv)2 – 1 |
| = t((u2 + v2)t – 2u). |
This is solved by t = 2u/(u2 + v2) so that,
| Q = | ( |
v2 – u2
u2 + v2
|
, |
2uv
u2 + v2
|
) | . |
While we already know what the circle looks like in the Euclidean plane where x and y are real, the argument above works over any field. Consider solutions over the rational numbers for example. Then, by scaling, we can suppose that u and v are coprime integers. Choosing the simple examples (u, v) = (1, 2) and (u, v) = (2, 3) gives rational points
|
||||||||
|
You may recognize these as corresponding to the well-known Pythagorean triples 32 + 42 = 52 and 52 + 122 = 132. In fact, multiplying our solution above by the denominator gives Euclid’s formula for generating such triples,
| (v2 – u2)2 + (2uv)2 = (u2 + v2)2. |
That almost completes the study of second order equations, although there are some loose ends or exceptional cases to clear up. We argued that since equation (4) is second degree in t with one solution at t = 0, we can factor to find the second solution. This can go wrong in a couple of ways. First, the left hand side of (4) can be identically zero, so that it is satisfied for all values of t and the entire line P + t(u, v) lies on the curve. However, this is only the case when p(x, y) decomposes as a product of two first order terms, and the curve is simply a union of two lines. We exclude such cases from consideration by requiring p(x, y) to be irreducible. Otherwise, we can always decompose into irreducible factors and look at each of the curves given by these factors.
Secondly, the argument above falls apart if the coefficient λ of the second order term in (4) is zero. Then, t = –μ/λ gives a division by zero and there is no second point of intersection Q. This never happened in the circle example described above, but it does for the hyperbola x2 – y2 = 1 shown in figure 2 whenever (u, v) is proportional to one of (1, 1) or (1, -1) (i.e., to one of the asymptotes displayed by dotted lines in the figure). More generally, substituting in the expression for p(x, y) on the left hand side of (4) and equating second order terms in t gives
| λ = au2 + buv + cv2. |
This is either irreducible, in which case the problem never occurs, or it decomposes as a product of two linear terms as for the hyperbola, giving at most two lines through P which do not intersect the curve at any other point. We can interpret this as intersecting the curve at infinity. This can be made more rigorous by looking at curves in the projective plane, which includes points at infinity.
Next, is it possible for two different lines through P to give the same second point of intersection? As two non-parallel lines intersect at only a single point, this is only possible if the second point Q is equal to P. This happens when the first order coefficient μ of t in (4) is equal to zero. We can compute
| μ = upx(x1, y1) + vpy(x1, y1). |
where px, py denote the partial derivatives of p with respect to x and y respectively. We assume that the point P is nonsingular, meaning that the gradient of p, (px, py), is not equal to zero. In that case, μ is only equal to zero when the line is tangent to the curve. This only occurs when (u, v) is parallel to (py, -px), so the argument above does indeed give a one to one parameterization of the curve (plus one or two points at infinity) by the projective line.
The only remaining exceptional case is when the curve is singular at P, so the gradient of p vanishes there. In that case, μ = 0 so that the second point Q is equal to P regardless of the direction of the line. This is the rather uninteresting case where the curve only has one point. For example, x2 + y2 = 0 which, over the real numbers, only consists of a single point at the origin.
Cubic Equations
With the warm-up complete, I now look at degree three polynomials, which are of the form
| p(x, y) = ax3 + bx2y + cxy2 + dy3 + ⋯ |
for coefficients a, b, c, d not all zero, and the ellipsis (⋯) represents terms of degree zero, one and two. We suppose that p is irreducible, so does not decompose as a product of a linear and a quadratic factor. So long as it contains no singular points where the gradient of p vanishes, the zero set of p is called an elliptic curve.
Let us describe how the ideas above can be extended to construct points on the curve given by p(x, y) = 0. Start with a point P on the curve. We could try proceeding as for the quadratic case and consider a line through P, then find other points of intersection. However, as it is cubic, a line will in general intersect at three points so, besides P, there will be two other points of intersection. Finding these requires solving a quadratic, which may not have any solutions in the field or, even if it does, requires taking a square root to describe the solutions. Therefore, the solutions cannot be found by the algebraic operations of addition, subtraction, multiplication and division alone.
Instead, let us consider two distinct points on the curve, P and Q. There will be a unique line through these, which will intersect the curve in three points. So, there is one point of intersection besides P and Q. Taking two points on the curve described by equation (1) above, the situation is as shown in figure 4 below.
The general equation of a line is (x + tu, y + tv) for constants x, y, u, v and its points of intersection with the curve are given by the formula
| p(x + tu, y + tv) = 0. | (5) |
This will be of degree up to three in t. If the line intersects the points P and Q at t = t1 and t = t2 then we can factor,
| p(x + tu, y + tv) = (t – t1)(t – t2)(λt + μ). |
for some constants λ, μ. These cannot both be equal to zero as, otherwise, the line (x + tu, y + tv) would lie on the curve, and p would have a linear factor so would not be irreducible. Except for the special case where λ vanishes, we obtain a third point of intersection R at t = –μ/λ. This is as shown in figure 4, and we have obtained a binary operation taking pairs P, Q of distinct points on the curve, to a third point R. I will denote this binary operation by P○Q = R.
There is one special case to consider, which is when λ = 0 so that there is no third point of intersection. Using the expression for p(x, y) we can compute,
| λ = au3 + bu2v + cuv2 + dv3. |
As it is a cubic, this can only vanish at 1 or 3 points corresponding to points (u, v) on the projective line at infinity, which we interpret as points at infinity of lines parallel to (u, v). Here, we identify points where (u, v) is scaled by a nonzero factor. In that case, for completeness, we can add these points at infinity to the curve and interpret R = P○Q as the point at infinity intersecting the line through P and Q.
We have described how, algebraically, given any two distinct points P and Q on the curve, we can find a third point R = P○Q. However, what happens if the two points are not distinct? Then, the argument above does not quite apply, since there is not a unique line passing through P and Q. Consider the case where the points are distinct, but are close. What happens to the slope of the line joining the points as we move Q towards P? As is well-known, it tends to the tangent at P. This does require working over the field of real or complex numbers where such limits are well-defined. However, the tangent line at P is well defined over any field. It is simply the line passing through P and parallel to (py, -px), where px, py denote, respectively, the partial derivatives of p with respect to x and y. So long as the line is taken as a tangent to the curve at P, the argument above applies. This does require the point P to be nonsingular, so that the gradient (px, py) at P is nonzero. As above, equation (5) describes the points of intersection of the line with the curve, and if it touches P at t = t1, then we have a double root. So, we can factor
| p(x + tu, y + tv) = (t – t1)2(λt + μ) |
and we find a second point of intersection at t = –λ/μ, which I will denote by P○P. This is shown in figure 5 below As previously, there is the special case with λ = 0 where there is no second point of intersection so, again, I consider it to give the point at infinity of the tangent line.
So far, we have seen how given one or two points on the curve, we can algebraically find another third point, given by the other point of interestion of the line through these points (or tangent to the curve if we have just one point). This gives a binary operator P○Q on the curve, although there can be exceptional cases where we get one of finitely many points at infinity.
Note that equality P○Q = R is the same as saying that the points are the three intersections (with multiplicity) of a line with the curve. So, it is unchanged if the order is permuted, giving Q○P = R and P○R = Q or,
| Q○P = P○Q, |
| P○(P○Q) = Q. |
There is one remaining special case to consider, which is where the curve contains a singular point P where the derivative of p vanishes. Two examples are shown in figure 6 below, both of which have a singular point at the origin. The one on the left is y2 = x3, which has a cusp, and the one on the right is y2 = x3 + x2, which has a self-intersection.
In fact, curves with a singular point P = (x, y) can be parametrized in a similar way as for conics described above. As any line (x + tu, y + tv) intersects the curve at P with multiplicity at least 2, we have
| p(x + tu, y + tv) = t2(λt + μ) |
and obtain a second point of intersection at t = –λ/μ, parameterizing the curve by the lines through P. Applying this to the curve y2 = x3 in figure 6 gives the parameterization (x, y) = (u2, u3) and, applying it to y2 = x3 + x2 gives (x, y) = (u2 - 1, u(u2 - 1)). So, the interesting examples with a deep structure are covered by the nonsingular cases.
The procedure outlined allows us to start from a finite set of points on an elliptic curve and generate a new point. Iteratively applying the construction will generate an infinite sequence of points, although there is no guarantee that these new points are not already in the set. In fact, as some elliptic curves only contain a finite set of rational points, it can happen that we eventually start obtaining the same points over again. An example is the curve x3 + y3 = 1 which, by Fermat’s Last Theorem, only has two finite rational solutions x = 0, y = 1 and x = 1, y = 0. Also, this method generates a countable sequence so, for curves over the real numbers which have uncountably many points, it will not construct them all. On the other hand, a result of the early 20th century — Mordell’s theorem — states that all of the rational points of an elliptic curve can be constructed in this way starting from a finite collection of initial points. Also, when working over a huge finite field, there will be many points on the curve, but they can usually all be constructed from a small initial collection by the method described here. In particular, the elliptic curve y2 = x3 + 7 used by Bitcoin, defined modulo the huge prime number p given above in (2) is cyclic, meaning that we can generate all points in this way starting from a single initial point.
Weierstrass normal form
The method above describes how we can construct new points on an elliptic curve from existing known points, using the standard field operations of addition, subtraction, multiplication, and division. It might help to clarify matters by writing out some explicit formulas. However, attempting this for a curve given by an arbitrary cubic polynomial would just get extremely messy. So, before working out such explicit formulas, we restrict to certain simplified polynomial equations known as the Weierstrass normal form,
| y2 = x3 + ax + b. | (6) |
It is known that all elliptic curves can be expressed like this by a change of variables (so long as the base field does not have characteristic 2 or 3), although that is not important here. We simply assume that we are given an elliptic curve of the form (6), which is the zero set of the polynomial
| p(x, y) = y2 – x3 – ax – b. |
Note that, as it only depends on y through its square, p is unchanged under reflecting about the x-axis (i.e., flipping the sign of y), so the elliptic curve is also symmetric about the x-axis.
Now, consider two distinct points P = (x1, y1) and P = (x2, y2) on the curve. We can derive the exact algebraic expression for the third point R = P○Q of intersection of the line passing through P and Q. Start by letting γ be the gradient of the line joining the points,
| γ = |
y2 – y1
x2 – x1
|
. |
Computing the polynomial p along the line y = y1 + (x - x1)γ gives
| p(x, y1 + (x - x1)γ) |
| = (y1 + (x - x1)γ)2 – x3 + ⋯ |
| = x2γ2 – x3 + ⋯ |
| = (x - x1)(x - x2)(γ2 - x1 - x2 - x) + ⋯ |
where the constant and first order terms in x have been ignored. As we know that the line passes through the curve at both x = x1 and x = x1, the ignored linear term in the final line must also vanish here, so is identically zero. Therefore, the third point of intersection occurs when γ2 - x1 - x2 - x = 0. So, R = (x′, y′) is given by the algebraic formula,
| x′ = γ2 – x1– x2, |
| y′ = y′1 + γ(x′ - x1). |
The formulas above also apply when the points coincide, P = Q = (x1, y1), except that γ is now set to the gradient of the tangent line,
| γ = |
dy
dx
|
= |
3x2 + a
2y
|
. |
The only situation where the explicit formulas above fail is when the point Q is just the reflection of P about the x-axis. In this case, the expression for γ gives a division by zero since the line is vertical, and only intersects the curve in two points. In that case, we say that the third intersection point is the point at infinity of the elliptic curve, which I will denote by 𝒪. This is the point at infinity of any vertical line, and P○Q = 𝒪. Similarly, 𝒪○P = Q is the reflection of P about the x-axis and, for completeness, we also set 𝒪○𝒪 = 𝒪. For an online calculator graphically showing these constructions for elliptic curves in the Weierstrass normal form, see Desmos.
Let’s look at a worked example with the elliptic curve y2 = x3 + 3. It can be seen by inspection that this contains the point P = (1, 2). Computing Q = P○P using the formulas above, we obtain γ = 3/4, so that x′ = -23/16 and y′ = 11/64, giving a second point
| Q = | ( |
-23
16
|
, |
11
64
|
) |
on the curve. We can go further and compute more points. Although P○Q would just get us back to the original point P, we can instead use the reflection of P about the x-axis, P′ = (1, -2). Applying the formulas above to P′○Q gives γ = -139/156 and, then,
| R = | ( |
1873
1521
|
, |
-130870
59319
|
) | . |
These constructions are shown in figure 7 below and, by continuing in this fashion, we can iteratively generate an infinite sequence of new points on the curve.
Finite Field Example
Let us consider the same curve y2 = x3 + 7 as used by Bitcoin except, here, we work modulo the much smaller prime p = 13. We already know that the curve is symmetric about the x-axis so, if it contains a point (x, y), then it also contains (x, -y). However, the integers modulo 13 also contain a nontrivial cube root of unity, ω = 3. That is ω3 = 1 (mod 13). This means that (ωx, y) is also on the curve. In fact, all of the 6 points Pij = (ωix, (-1)jy) will be on the curve for integers 1 ≤ i ≤ 3 and 1 ≤ j ≤ 2. Multiplying x by powers of ω and y by powers of -1 is a symmetry group of order 6, partitioning all of the finite points of the curve into groups of 6. Doing a straightforward check, there are in fact 6 points in total,
| P11 = (7, 5), | P12 = (7, 8), | |
| P21 = (8, 5), | P22 = (8, 8), | |
| P31 = (11, 5), | P32 = (11, 8), |
which, together with the point 𝒪 at infinity, makes up the elliptic curve. Using the explicit formula, we can compute
| P11○P11 = P22, |
| P11○P21 = P31, |
| P11○P31 = P21, |
| P11○P22 = P11, |
| P11○P32 = P32. |
Together with Pi1○Pi2 = 𝒪, all other compositions follow from these in conjunction with the symmetry mentioned.
What about huge primes, such as the 256 bit one used by Bitcoin? First, using p as given by (2), it is straightforward to see that p – 1 is a multiple of 3. This implies that there does exist a nontrivial cube root of unity modulo p, just as in the example above, so again there is a symmetry group of order 6 and points on the curve can be partitioned into groups of size 6.
More generally, consider a finite field of size q, which must be a power of a prime. We can find points on the curve by a straightforward random search. Choose any random value of x and set z = x3 + ax + b. We need this to be a square, which can be tested by computing z(q - 1)/2. If the result is 1, then z is a square . As half of the elements of Fq are squares, this will have a 50% chance of succeeding and, if it does not, then just choose a different value of x and try again. Finally, compute the square root of z to obtain y. In the case that p + 1 is a multiple of 4, as with the value of q = p used by Bitcoin, the square root can be computed by y = z(p + 1)/4. More generally, the Tonelli–Shanks algorithm can be used. This argument suggests that about half of the possible values of x correspond to a point on the curve and, when it does, we obtain two of them (by reflection about the x-axis). So, the total number of points should be of the order of q. In fact, using a probabilistic heuristic, assuming independence for all values of x suggests a standard deviation of √q for the number of points. In fact, Hasse’s theorem provides rigorous bounds on the number of points N (including points at infinity),
| q + 1 – 2√q ≤ N ≤ q + 1 + 2√q. |
This is a rather advanced result, being equivalent to a special case of the Riemann Hypothesis over function fields (which are the only versions of the generalised Riemann Hypothesis that have been proven). Applying this with q = p = 13 as above gives 7 ≤ N ≤ 21 so the result we found, N = 7, was right at the lower bound. For the secp256k1 curve used by Bitcoin, the number of points is known to be
expressed in hexadecimal. This is about,
| N | ≈ 2256 – 2128 – 2126 – 2122 |
| ≈ p – 1.3√p. |
Zero Knowledge 