# 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 redthe 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 abovethe 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 2*m* 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:

## Comments