Doubling Points in A Finite Field
Doubling points in a finite field becomes important and central to the process of efficiently calculating multiples of a point - that is, kP where k is some constant integer. When dealing with large numbers we can use the doubling process to quickly calculate any multiple, k. As a basic example - if we want to know what 31P is, it is faster to calculate the values of 2P, 4P, 8P and 16P, and then add those values together, to get:
((((16P + 8P) + 4P) + 2P) + P) = 31P
for a total of 8 calculations, than it is to do the 30 calculations it would take to find the values for 2P, 3P, 4P, ... 30P, 31P.
This example reveals the "worst case" scenario for calculating kP where k is any value equal to or less than 31. This process allows us to find kP for any value of k in less than 2n calculations, when k < 2^{n+1} (Washington, L. C., 2008, pp16-17, Example 2.1).
Thus, we will spend some time exploring the process of doubling points in an elliptic field. Below are a number of examples, starting from other points on the curve:
modulus 13 (the curve explored previously in the article Arithmetic In A Finite Field)
Points of Interest
Note, with each example below:
the point we are doubling, P - marked in red
the gradient of the line is variable - always an integer value (mod 13) - as calculated using the Formal Derivative, and the process of modular division described above
the tangent line, in the form y = mx + b, will always re-enter the left-hand side of the space at y = b
the tangent line generated from each point crosses the top/bottom border the same number of times as the calculated "slope" value of the tangent, m
R and 2P are always each other's additive inverse, reflected across the line of reflection, at y = p/2
the tangent line always ends up back at the starting point
4, 5, and 6, above, are all attributes of the facts that:
we are working in a integer-sized "square" space, of size "p x p"
all values related to the curve and its tangent must be integer values, and can always be converted to values between 0 <= x < p
the tangent line must repeat after m number of interactions with the top/bottom border.
A simple way to understand this 3rd limitation is to see that the triangles, created by the tangent line are p units high, and, in order to be the correct angle ("slope"), the triangle they create must be p/m units wide at the top/bottom (so that the "rise over run" calculation for the slope of the lines works). As the length of that side of each triangle equals p/m, there must be 2m of these triangles, to fill the space - that is, the base / top of each triangle must be m.
P = (0, 1)
P = (0, 12)
P = (1, 4)
P = (1, 9)
P = (4, 2)
For animation purposes - sometimes it makes more sense to go "backwards". When R is "on the left" of P - that is, when the x value for R is less than the x value for P, then it makes more sense, in an animation of the connection between them, to draw the line downward and to the left first, so that the tangent line being drawn doesn't need to cross the vertical borders of the space in which it is being drawn, before passing through R.
NOTE: it doesn't matter which direction you start. In the end the tangent line will meet the correct point. It's just it gets there more clearly, for animation purposes, if you happen to know what the value R is, compared to P, and you can move in the simplest direction first.
P = (5, 1)
P = (5, 12)
The singular (non-reflected) points at y = 0, have a tangent that is a vertical line. This can be understood, loosely, by thinking about what happens with an elliptic curve in the Reals, when y = 0, at the point of reflection on the x-axis - that is, the tangent line approaches a vertical line, as y approaches 0, from both directions, and clearly becomes a vertical line (on the smooth curve), at that point.
It can also be understood, loosely, by considering the equation of the slope of the tangent:
which approaches infinity (or -ve infinity), as y approaches 0. This concept of "approaches" in a discrete field is not well defined, but the concept, and comparison with the situation in the field or Real numbers still helps to intuitively support the idea of vertical tangent.
A more rigorous investigation of the definition of a tangent in a finite field, for an elliptic curve, using Homogenous Equations, and The Projective Plane, is not covered, in these documents, but may be added at a later date.
P = (7, 0)
P = (8, 1)
P = (8, 12)
Sometimes, the value of R is P itself - for example, at the point P = (10, 6):
That is, in general, when:
in which case, the tangent line from P = (x_1, y_1) will meet itself back at R= (x_1, y_1). Leading to the idea that:
That is:
This is equivalent to the point, on an elliptic curve in the field of Real numbers, where the tangent line is not vertical, but only passes through one point on the curve. That is, the calculation of the cubic derived by finding where the tangent line intersects with the curve has one root (a "triple" root) which occurs when the the curvature of the elliptic curve (the second derivative) is 0.
As visualised here:
Two examples
Following are animations of drawing the tangent line from these two points (which are, clearly, always going to be the additive inverse of each other, due the symmetrical nature of the curve).
P = (10, 6)
P = (10, 7)
Horizontal Tangents
In a elliptic curve in a the field of Real numbers (depending on the specific of the curve) there are sometimes points where the tangent line is horizontal. The two points (on an elliptic curve in the Weierstrass form) where this is true are symmetrically reflected across the x-axis.
While this is not true of the equation:
in the field of Real numbers - a visual example of other equations in the field of Real numbers, that show this property, can easily be found:
This happens in finite fields as well:
P = (11, 2)
P = (11, 11)
Final Points
Finally, the last two points on this curve are points with no particular properties, over and above the previous points we have considered:
