# Arithmetic in a Finite field

*The operations of adding and doubling points on elliptic curves defined over finite fields form the cornerstone of elliptic curve cryptography (ECC), a key area of modern cryptographic systems. These operations are not only mathematically interesting but also critical for ensuring secure digital communications, encryption, and digital signatures.*

Below we will investigate some of the calculations involved in doubling points in a finite field - the Formal Derivative and division in a finite field (the multiplicative inverse). Finally, we will investigate the process of adding points in a finite field.

## Importance in Cryptography

### Efficiency and Security

**Finite Field Operations**: When elliptic curves are defined over finite fields (__Washington____, L. C., 2008,____ pp95-142, ____Chapter 4__) (such as *Fp* where *p* is a prime number), the group operations (addition and doubling of points) are __discrete and cyclic__. This discreteness provides a controlled environment conducive to defining hard problems such __the Elliptic Curve Discrete Logarithm Problem (ECDLP)__ (__Washington____, ____L. C., 2008,____ pp143-168, ____Chapter 5__), which is __computationally infeasible__ to solve efficiently with __current technology__ and forms the basis of security in ECC

**Hard Problems**: The security of ECC relies on the difficulty of reversing these group operations, particularly the __ECDLP__, where given two points *P* and *Q *on the curve, finding an integer *k* such that *Q *= *kP* (i.e., *P* added to itself *k* times) is computationally hard.

### Practical Application

**Digital Signatures and Key Exchange**: Operations such as point addition and doubling are fundamental for algorithms like __ECDSA (Elliptic Curve Digital Signature Algorithm)__ (__Washington____, L. C., 2008,____ pp179-180, ____Section 6.6__)and __ECDH (Elliptic Curve Diffie-Hellman)__ (__Washington____, L. C., 2008,____ pp170-173, ____Section 6.2__). These protocols utilise the properties of elliptic curves over finite fields to create secure digital signatures and facilitate secure key exchange mechanisms, respectively.

## Differences from Real Fields

### Closure and Finite Nature

**Finite Fields**: In finite fields, the values of the points and coefficients are taken modulo a prime *p* ensuring that all possible results of point operations remain within a finite set of values. This provides the necessary __closure__ and finiteness that is ideal for digital systems, which inherently rely on finite data representations.

**Real Fields**: In contrast, operations in real fields involve continuous values and do not naturally lend themselves to the modular arithmetic crucial for defining and securing cryptographic operations. __Real numbers lead to issues with precision and practical implementation in digital systems__ due to their __infinite decimal expansions__.

### Visualisation and Computation

**Discrete vs. Continuous**: Points on elliptic curves over real numbers can be visualised (below) as smooth continuous curves, making them great for theoretical analysis and understanding. However, elliptic curves over finite fields look quite different (left); they consist of discrete points which do not form a continuous line, aligning better with digital computation that requires discrete steps and finite states.

**Predictability and Security**: The predictable nature of real number operations (and specifically, relatively simple __reversibility of operations__) can be a drawback in security contexts, where __unpredictability and hardness of problem-solving are crucial__. Finite fields introduce a level of unpredictability, and irreversibility essential for cryptographic security.

This is analogous to the difficulty / irreversibility of the factorisation of the product of two large prime numbers, in __the RSA encryption process__. Both problems rely on the mathematical difficulty of reversing a process that is computationally easy to perform but hard to invert.

## The Process - an example

Take a specific elliptic curve, say:

modulus 13.

Find all the integer values of *x* and *y* for which the equation of the elliptic curve holds true. These points are not always as obvious, intuitively - or as easy to calculate - as they are for the elliptic curve defined in the field of Real numbers.

For example, when *y = 11*, and *x = 4*:

and:

However, when taken modulus 13:

And so *(4, 11)* is a solution to the equations, i.e. a point on the elliptic curve.

**NOTE**: because of the symmetrical nature of the curve, if *(x, y)* is on the curve, so is *(x, -y) = (x, p-y) mod p*. And so we know immediately that *(4, -11) = (4, p-11) = (4, 2) mod 13* is on the curve - which can be confirmed by calculating: *2^2 = 4*.

The list of points on this elliptic curve is:

(0, 1), (0, 12), (1, 4), (1, 9), (4, 2), (4, 11), (5, 1), (5, 12),

(7, 0), (8, 1), (8, 12), (10, 6), (10, 7), (11, 2), (11, 11), (12, 5), (12, 8)

As seen graphed here:

### Arithmetic on an Elliptic Curve in a Finite Field

In a finite field, the "gradient" can be found by the same method as for an elliptic curve in the field of real numbers - however: __we must invoke the concept of the Formal Derivative, to do so rigorously__, as finite fields are without a concept of a limit (or the concept of "approaching" a value, in infinitesimally small steps), upon which to define the idea of finding a slope, as two points become one.

Furthermore, the concept of "division" must be altered. All division, in these calculations, must be done in a way that adheres to the process of division for modular arithmetic.

In modular arithmetic, __we focus on the fact that division should "undo multiplication" (see: Section 2.1 of this publication)__. This is achieved by multiplying the dividend by __the modular multiplicative inverse__ of the divisor. We know that the modular inverse must exist, because the elliptic curve is defined on a field - and __all values in a field have a modular (multiplicative) inverse__.

First, we __find the equation for the slope of the tangent to the curve__. That is:

this would mean:

Substituting in the values for the point we used before, *(4, 11)*, we get:

But (and this is the important part, with reference to division, in a finite field), in order to divide by *9*, you multiply by its (*9's*) __modular multiplicative inverse__. The modular multiplicative inverse of *9* is the number, in the field, which when multiplied by *9* is equivalent to: *1 mod 13*.

To work out the modular multiplicative inverse of *9 mod 13*, we can use __a few different approaches__. In this case, we will use Fermat's Little Theorem. That is:

that is, the modular multiplicative inverse of *9 mod 13* is *3*.

So now we can calculate the integer (*mod 13 *) value for *dy/dx* - that is:

and so, the gradient of the tangent of:

at the point *(4, 11)*, is *4*. Leading us to conclude that the tangent line to the curve that passes through *(4, 11)* has the equation:

This line *y = 4x + 8* is:

tangent to the curve

*y^2 = x^3 + x + 1*at P = (4, 11)guaranteed to pass through one other point on the curve (see

__previous calculations__)will ONLY pass through ONE other point on the curve (see the fact that a line, passing through more than 2 points on (or that is tangent to) an elliptic curve describes a cubic, and therefore has a maximum of three solutions, in

__previous calculations__)

**NOTE**: we take the point that it crosses to be:

*R = -2P*

and its point of reflection (*mod p*) is:

-R = (x_r, -y_r) = (x_r, p-y_r) = 2P

and so, we have found the position of 2P.

### Visualising the tangent to the Curve in the Finite Field

Following is an animation, that helps to visualise the behaviour of the tangent to an elliptic curve:

in as finite field (modulus 13).

By drawing a tangent line from our "point of interest, on the curve", we see the following:

**Note**:

the point we are doubling, at

*P = (4, 11)*the line coming from it, at a slope of

*4*, traversing the space between*0 <= x < 13*, and*0 <= y < 13*the fact that, like the physics of the 80s game Asteroids, when the line reaches a border of the space, it re-enters the space, on the opposite side of the space, at the same gradient (NOTE: the idea to visualise the tangent line as a line that crosses the border of the space, and back in the other side was taken from here: "

__A (relatively easy to understand) primer on elliptic curve cryptography__".the points

*R = (8, 1)*, and*2P = (8, 12)*, and the vertical line joining them, appear as the tangent crosses the point*R*, because this indicates that*2P + R = the point at infinity*and that the additive inverse of*R*is*2P*the tangent line eventually crosses the

*y-axis*at*y = 8*- as clear from the equation*y = 4x + 8*the tangent line continues through the space and eventually ends up back at

*P*, having passed through the top/bottom of the space*4*times (the same as the value of the tangent slope). NOTE: it is necessary that the tangent line eventually meet*P*again, after*m*number of vertical transitions through the top/bottom of the space, as it also does not matter which direction from*P*the tangent line is drawn. It will always pass through*P*.

To show that the point at which the tangent line intersects with the curve again is the right point, see the following:

which shows that the three points of intersection of the curve and the tangent line at *P = (4, 11)* are:

*x = 4* (twice), and

*x = 8*

Putting x = 8 back into the equation for the tangent line, we get:

which further shows that the other point of intersection between the tangent line and the curve is:

*R = (8, 1)*

as shown in the animation above.