FUNtastic Elliptic Curves

Bhaskar S

12/16/2022

Overview

An Elliptic Curve is a geometric plane curve that is generated by the following polynomial equation of cubic ($3^{rd}$) degree:

$y^2 = x^3 + a.x + b$ $\color{red} ..... (1)$

with the following discriminant constraint:

$4.a^3 + 27.b^2 \ne 0$

Note that the Elliptic Curve has nothing to do with the geometric shape - Ellipse.

The following is the Elliptic Curve for the equation $y^2 = x^3 -2.x + 2$:

Figure.1

An observation about an Elliptic Curve - it will be symmetrical in shape along the x-axis. This implies any point $P$ on the curve has an Inverse point $-P$ on the opposite axis.

Mathematical Intuition

Elliptic Curve over Group

Before we proceed further, we will need to define some mathematical concepts.

A Group $G$ is a set of elements, along with a single addition operation (denoted as $+$), that has the following properties:

an operation on two elements $a$ and $b$ from the Group is closed. That is, the result of an operation is an element $c$ that belongs to the Group. In mathematical terms, $a + b = c$ implies ${a, b, c} \in G$
an operation on two elements $a$ and $b$ from the Group is commutative. In mathematical terms, $a + b = b + a$
an operation on three elements $a$, $b$, and $c$ from the Group is associative. In mathematical terms, $a + (b + c) = (a + b) + c = a + b + c$
there exists an Identity element $0$ such that $a + 0 = a$
for every element $a$, there exists an Inverse element $-a$ such that $a + (-a) = 0$

An Abelian Group is a Group in which the application of the operation $+$ does not change the result because of the order of the two elements involved in the operation. In other words, in an Abelian Group the operator $+$ is both associative and commutative.

The rules of operation on a Group are often referred to as the Group Law.

An Elliptic Curve is an Abelian Group with an addition $+$ operation and an Identity point $\mathcal{O}$, which is NOT the same as the point of origin $(0, 0)$, but a point at infinity on a line along the y-axis. If $P$, $Q$, and $R$ are points on the Elliptic Curve and $-P$ is the inverse of $P$, then the Elliptic Curve Abelian Group has the following Group Law:

$P + \mathcal{O} = \mathcal{O} + P = P$
$P + (-P) = \mathcal{O}$
$P + Q = Q + P = \mathcal{O}$
$P + (Q + R) = (P + Q) + R = \mathcal{O}$

Let us now look at the Elliptic Curve Group Law from an Geometric angle.

Let $P$, $Q$, and $R$ be the three points on an Elliptic Curve as shown in the illustration below:

Figure.2

From the Group Law for Elliptic Curve, we know the following fact:

$P + Q + R = \mathcal{O}$

That is:

$P + Q = -R$

Geometrically, if we draw a line that passes through the points $P$ and $Q$ as shown in the Figure.2 above, the line will intersect the Elliptic Curve at a third point $R$. The inverse of the point $R$ is the point $-R$. Therefore, the result of the addition operation $P + Q$ is the reflected point $-R$.

Note that we added the Identity point $\mathcal{O}$ to the Elliptic Curve Abelian Group. To answer why, look at the case when $Q = -P$ as shown in the illustration below:

Figure.3

As is evident from Figure.3 above, the line that passes through $P$ and $-P$ is a vertical line that is parallel to the y-axis and never intersects with the Elliptic Curve at a third point. The line just goes to infinity in both directions. Hence the need for a point that represents the point of infinity $\mathcal{O}$.

Now for a very interesting case - as the point $Q$ moves closer and closer to the point $P$, the point $R$ will get closer closer to the value of $2P$. In other words, when $Q$ equals $P$, the line will become a tangent at $P$ and we will have $P + Q = P + P = 2P$, with the point $R$ essentially representing $2P$ as shown in the illustration below:

Figure.4

Let us now look at the Elliptic Curve Group Law from an Algebraic angle.

Once again let $P = (x_1, y_1)$, $Q = (x_2, y_2)$, and $R = (x_3, y_3)$ be the three points on an Elliptic Curve as shown in the Figure.2 above.

The equation of any line is given as follows:

$y = m.x + c$ $\color{red} ..... (2)$

where $m$ is the slope of the line and $c$ the intercept of the line.

Using equations (1) and (2) from, above we get:

$(m.x + c)^2 = x^3 + a.x + b$

That is:

$m^2.x^2 + 2.m.c.x + c^2 = x^3 + a.x + b$

Simplifying, we get:

$x^3 - m^2.x^2 + a.x - 2.m.c.x + b - c^2 = 0$ $\color{red} ..... (3)$

Since we know the coordinates for two of the points $P$ and $Q$, the slope of the line $m$ can be computed is as follows:

$m = \bbox[pink,2pt]{\Large{\frac{y_2 - y_1}{x_2 - x_1}}}$ $\color{red} ..... (4)$

From Algebra, we know that a cubic ($3^{rd}$ degree) equation has three roots and is represented as follows:

$(x - p)(x - q)(x - r)$ $\color{red} ..... (5)$

Expanding equation (5), we get:

$x^3 + (-p -q -r).x^2 + (p.q + p.r + q.r).x + p.q.r$ $\color{red} ..... (6)$

From the equations (3) and (6), equating the coefficients of the second term, we get:

$-m^2 = (-p -q -r)$

Simplifying, we get:

$m^2 = p + q + r$ $\color{red} ..... (7)$

Given that we know the coordinates for two points $P$ and $Q$ on the line and they intersect with the curve, the x-coordinates form the roots of the cubic eqaution (1).

That is:

$m^2 = x_1 + x_2 + x_3$

Or:

$x_3 = \bbox[pink,2pt]{m^2 - x_1 - x_2}$ $\color{red} ..... (8)$

Once we know the slope $m$ and $x_3$, we can find $y_3$ as follows using equation (4):

$m = \Large{\frac{y_3 - y_1}{x_3 - x_1}}$

Or:

$y_3 = y_1 + m.(x_3 - x_1)$

Note that we need the reflected point of $y_3$.

Therefore:

$-y_3 = -(y_1 + m.(x_3 - x_1))$

Or:

$y_3 = \bbox[pink,2pt]{m.(x_1 - x_3) - y_1}$ $\color{red} ..... (9)$

When the two points $P$ and $Q$ are not equal, then the equation (8) and (9) from above hold true.

What if the points $P$ and $Q$ are equal ???

Then the line becomes tanget at the point $P$ and we can find the slope of the line $m$ by taking the derivative of equation (1).

That is:

$\Large{\frac{d}{dx}}$ $y^2 = \Large{\frac{d}{dx}}$ $(x^3 + a.x + b)$

Or:

$2.y.y^{\prime} = 3.x^2 + a$

Simplifying, we get:

$y^{\prime} = m = \bbox[pink,2pt]{\Large{\frac{3.x^2 + a}{2.y}}}$ $\color{red} ..... (10)$

Now that we know the slope $m$, we can use the equation (8) from above to find the new x-coordinate as follows:

$x_3 = m^2 - x_1 - x_2 = m^2 - x_1 - x_1$ (since $x_2 = x_1$)

Or:

$x_3 = \bbox[pink,2pt]{m^2 - 2.x_1}$ $\color{red} ..... (11)$

Now that we know $x_3$, we can find the reflected $y_3$ using equation (9) from above.

Let us look at an example for the case where we have two points $P$ and $Q$.

Example-1	Given the Elliptic Curve $y^2 = x^3 - 34.x + 37$ along with the two points $P = (1, 2)$ and $Q = (6, 7)$, find the point for $P + Q$
From the given Elliptic Curve equation, we know $a = -34$ and $b = 37$ First let us make sure it is an Elliptic Curve by checking $4.a^3 - 27.b^2 \ne 0$ That is, $4.(-34)^3 - 27.(37)^2 = -194179 \ne 0$ The given equation is indeed an Elliptic Curve. Next, given the two points $P \ne Q$, we can use the equations (4) to determine the slope $m$ That is, $m = \Large{\frac{7 - 2}{6 - 1}}$ $= \Large{\frac{5}{5}}$ $= 1$ Since we know the slope $m$ and the x-coordinates for the two points, we can use the equation (8) to find the x-coordinate for the point $P + Q$ That is, $x_3 = m^2 - x_1 - x_2 = 1^2 - 1 - 6 = -6$ Now that we know the x-coordinate for the point $P + Q$, we can use the equation (9) to find the y-coordinate for the point $P + Q$ That is, $y_3 = m.(x_1 - x_3) - y_1 = 1.(1 - (-6)) - 2 = (1 + 6) - 2 = 5$ Therefore, $P + Q = (-6, 5)$

Example-1

Given the Elliptic Curve $y^2 = x^3 - 34.x + 37$ along with the two points $P = (1, 2)$ and $Q = (6, 7)$, find the point for $P + Q$

From the given Elliptic Curve equation, we know $a = -34$ and $b = 37$

First let us make sure it is an Elliptic Curve by checking $4.a^3 - 27.b^2 \ne 0$

That is, $4.(-34)^3 - 27.(37)^2 = -194179 \ne 0$

The given equation is indeed an Elliptic Curve.

Next, given the two points $P \ne Q$, we can use the equations (4) to determine the slope $m$

That is, $m = \Large{\frac{7 - 2}{6 - 1}}$ $= \Large{\frac{5}{5}}$ $= 1$

Since we know the slope $m$ and the x-coordinates for the two points, we can use the equation (8) to find the x-coordinate for the point $P + Q$

That is, $x_3 = m^2 - x_1 - x_2 = 1^2 - 1 - 6 = -6$

Now that we know the x-coordinate for the point $P + Q$, we can use the equation (9) to find the y-coordinate for the point $P + Q$

That is, $y_3 = m.(x_1 - x_3) - y_1 = 1.(1 - (-6)) - 2 = (1 + 6) - 2 = 5$

Therefore, $P + Q = (-6, 5)$

Now, let us look at an example for the case where there is just one point $P$.

Example-2	Given the Elliptic Curve $y^2 = x^3 - 7.x + 10$ along with a point $P = (1, 2)$, find the point for $P + P = 2P$
From the given Elliptic Curve equation, we know $a = -7$ and $b = 10$ First let us make sure it is an Elliptic Curve by checking $4.a^3 - 27.b^2 \ne 0$ That is, $4.(-7)^3 - 27.(10)^2 = -4072 \ne 0$ The given equation is indeed an Elliptic Curve. Next, given a single point $P$, we can use the equations (10) to determine the slope $m$ That is, $m = \Large{\frac{3.1^2 + (-7)}{2.2}}$ $= \Large{\frac{-4}{4}}$ $= -1$ Since we know the slope $m$ and the x-coordinate for the point $P$, we can use the equation (11) to find the x-coordinate for the point $2P = P + P$ That is, $x_3 = m^2 - 2.x_1 = (-1)^2 - 2.1 = -1$ Now that we know the x-coordinate for the point $2P = P + P$, we can use the equation (9) to find the y-coordinate for the point $2P = P + P$ That is, $y_3 = m.(x_1 - x_3) - y_1 = -1.(1 - (-1)) - 2 = -1.(2) - 2 = -4$ Therefore, $2P = P + P = (-1, -4)$

Example-2

Given the Elliptic Curve $y^2 = x^3 - 7.x + 10$ along with a point $P = (1, 2)$, find the point for $P + P = 2P$

From the given Elliptic Curve equation, we know $a = -7$ and $b = 10$

First let us make sure it is an Elliptic Curve by checking $4.a^3 - 27.b^2 \ne 0$

That is, $4.(-7)^3 - 27.(10)^2 = -4072 \ne 0$

The given equation is indeed an Elliptic Curve.

Next, given a single point $P$, we can use the equations (10) to determine the slope $m$

That is, $m = \Large{\frac{3.1^2 + (-7)}{2.2}}$ $= \Large{\frac{-4}{4}}$ $= -1$

Since we know the slope $m$ and the x-coordinate for the point $P$, we can use the equation (11) to find the x-coordinate for the point $2P = P + P$

That is, $x_3 = m^2 - 2.x_1 = (-1)^2 - 2.1 = -1$

Now that we know the x-coordinate for the point $2P = P + P$, we can use the equation (9) to find the y-coordinate for the point $2P = P + P$

That is, $y_3 = m.(x_1 - x_3) - y_1 = -1.(1 - (-1)) - 2 = -1.(2) - 2 = -4$

Therefore, $2P = P + P = (-1, -4)$

Elliptic Curve over Field

Switching gears on to the next set of concepts.

A Field $F$ is a set of elements, along with two operations - addition (denoted as $+$) and multiplication (denoted as $.$ (dot)), with the following properties:

an operation on two elements $a$ and $b$ from the Field is closed. That is, the result of an operation is an element $c$ that belongs to the Field. In mathematical terms, $a + b = c$ implies ${a, b, c} \in F$. Also, $a . b = d$ implies ${a, b, d} \in F$
an operation on two elements $a$ and $b$ from the Field is commutative. In mathematical terms, $a + b = b + a$. Also, $a . b = b . a$
an operation on three elements $a$, $b$, and $c$ from the Group is associative. In mathematical terms, $a + (b + c) = (a + b) + c = a + b + c$. Also, $a . (b . c) = (a . b) . c = a . b . c$
there exists an Identity element $0$ for the addition operation such that $a + 0 = a$ and $1$ for the multiplication operation such that $a . 1 = a$
for every element $a$, there exists an Inverse element $-a$ for the addition operation such that $a + (-a) = 0$ and $a^{-1}$ for the multiplication operation such that $a . a^{-1} = 1$

A Finite Field is a Field with a finite set of elements.

Modular Arithmetic is an arithmetic number system, where the numbers lie in the interval $(0, n]$ (or wrap around $0$ to $n-1$) the a specifc value of $n$ called the Modulus.

Mathematically, given a Modulus number $n$, two numbers $a$ and $b$ are said to have a Modulo relationship if $a = b + k.n$, where $k$ is some multiple. This Modulo relationship is often represent using the following representation:

$a \equiv b \: (mod \: n)$

The following are few IMPORTANT rules to follow when working with Modular Arithmetic:

$(a + b) \: (mod \: n) = ((a \: (mod \: n)) + (b \: (mod \: n)) \: (mod \: n))$
$(a . b) \: (mod \: n) = ((a \: (mod \: n)) . (b \: (mod \: n)) \: (mod \: n))$
$\Large{\frac{a}{b}}$ $\: (mod \: n) = (a . b^{-1}) \: (mod \: n)$. Note that $b^{-1} \: (mod \: n)$ implies $k.b \equiv 1 \: (mod \: n)$. $b^{-1}$ is the Multiplicative Inverse

The following are few examples relating to Modular Arithmetic:

$17 \: (mod \: 13) = 4$
$-11 \: (mod \: 17) = 6$
$7^{-1} \: (mod \: 19) = 11$

Often, the elements of a Finite Field are defined using the constraints of integer modulo p, where $p$ is an odd prime number, and denoted using $\mathbb{F}_p$.

Now that we have covered the core concepts, it is time to shift to an Elliptic Curve whose elements are in $\mathbb{F}_p$. The Elliptic Curve equation from (1) can be re-written as follows:

$y^2 \equiv x^3 + a.x + b \: (mod \: p)$ $\color{red} ..... (12)$

with the following discriminant constraint:

$4.a^3 + 27.b^2 \not\equiv 0 \: (mod \: p)$

The derivations of the equations (4), (8), (9), (10), and (11) for the Elliptic Curve are all valid, except for the modulo $p$ constraint.

Given two points $P$ and $Q$, the third point $R$ can be determinded as follows:

$m = \bbox[pink,2pt]{\Large{(\frac{y_2 - y_1}{x_2 - x_1})}\normalsize{\: (mod \: p)}}$ $\color{red} ..... (13)$

$x_3 = \bbox[pink,2pt]{[m^2 - x_1 - x_2] \: (mod \: p)}$ $\color{red} ..... (14)$

$y_3 = \bbox[pink,2pt]{[m.(x_1 - x_3) -y_1] \: (mod \: p)}$ $\color{red} ..... (15)$

Given one point $P$, the point $R$ can be determinded as follows:

$m = \bbox[pink,2pt]{[(3.x^2 + a).(2.y)^{-1}] \: (mod \: p)}$ $\color{red} ..... (16)$

$x_3 = \bbox[pink,2pt]{m^2 - 2.x_1 \: (mod \: p)}$ $\color{red} ..... (17)$

Given that we know the slope $m$ and $x_3$, we can find the reflected $y_3$ using equation (15) from above.

The multiplication of a point $P$ on an Elliptic Curve over $\mathbb{F}_p$ with a scalar $n$ is represented as $n.P$ is nothing more than adding $P$ to itself $n$ times.

That is:

$n.P \: (mod \: p) = (P + P + ... + P) \: (mod \: p)$, where the point $P$ is added $n$ times

Let us look at an example for the case where we have two points $P$ and $Q$.

Example-3	Given the Elliptic Curve $y^2 = x^3 + x + 1$ over $\mathbb{F}_5$ along with the two points $P = (3, 1)$ and $Q = (2, 4)$, find the point for $P + Q$ over $\mathbb{F}_5$
From the given Elliptic Curve equation, we know $a = 1$ and $b = 1$ First let us make sure it is an Elliptic Curve by checking $4.a^3 - 27.b^2 \not\equiv 0 \: (mod \: 5)$ That is, $4.(1)^3 - 27.(1)^2 = -23 \: (mod \: 5) = 2 \ne 0$ The given equation is indeed an Elliptic Curve. Next, given the two points $P \ne Q$, we can use the equations (13) to determine the slope $m$ That is, $m = \Large{\frac{4 - 1}{2 - 3}}\normalsize{\: (mod \: 5)}$ $= \Large{\frac{3}{-1}}\normalsize{\: (mod \: 5)}$ $= -3 \: (mod \: 5) = 2$ Since we know the slope $m$ and the x-coordinates for the two points, we can use the equation (14) to find the x-coordinate for the point $P + Q$ over $\mathbb{F}_5$ That is, $x_3 = [m^2 - x_1 - x_2] \: (mod \: 5) = [2^2 - 3 - 2 = -1] \: (mod \: 5) = 4$ Now that we know the x-coordinate for the point $P + Q$, we can use the equation (15) to find the y-coordinate for the point $P + Q$ over $\mathbb{F}_5$ That is, $y_3 = [m.(x_1 - x_3) - y_1] \: (mod \: 5) = [2.(3 - 4) - 1] \: (mod \: 5) = [2.(-1) - 1] \: (mod \: 5) = -3 \: (mod \: 5) = 2$ Therefore, $P + Q = (4, 2)$ over $\mathbb{F}_5$

Example-3

Given the Elliptic Curve $y^2 = x^3 + x + 1$ over $\mathbb{F}_5$ along with the two points $P = (3, 1)$ and $Q = (2, 4)$, find the point for $P + Q$ over $\mathbb{F}_5$

From the given Elliptic Curve equation, we know $a = 1$ and $b = 1$

First let us make sure it is an Elliptic Curve by checking $4.a^3 - 27.b^2 \not\equiv 0 \: (mod \: 5)$

That is, $4.(1)^3 - 27.(1)^2 = -23 \: (mod \: 5) = 2 \ne 0$

The given equation is indeed an Elliptic Curve.

Next, given the two points $P \ne Q$, we can use the equations (13) to determine the slope $m$

That is, $m = \Large{\frac{4 - 1}{2 - 3}}\normalsize{\: (mod \: 5)}$ $= \Large{\frac{3}{-1}}\normalsize{\: (mod \: 5)}$ $= -3 \: (mod \: 5) = 2$

Since we know the slope $m$ and the x-coordinates for the two points, we can use the equation (14) to find the x-coordinate for the point $P + Q$ over $\mathbb{F}_5$

That is, $x_3 = [m^2 - x_1 - x_2] \: (mod \: 5) = [2^2 - 3 - 2 = -1] \: (mod \: 5) = 4$

Now that we know the x-coordinate for the point $P + Q$, we can use the equation (15) to find the y-coordinate for the point $P + Q$ over $\mathbb{F}_5$

That is, $y_3 = [m.(x_1 - x_3) - y_1] \: (mod \: 5) = [2.(3 - 4) - 1] \: (mod \: 5) = [2.(-1) - 1] \: (mod \: 5) = -3 \: (mod \: 5) = 2$

Therefore, $P + Q = (4, 2)$ over $\mathbb{F}_5$

Now, let us look at an example for the case where there is just one point $P$.

Example-4	Given the Elliptic Curve $y^2 = x^3 + x + 1$ over $\mathbb{F}_5$ along with a point $P = (0, 1)$, find the point for $5P$ over $\mathbb{F}_5$
From the given Elliptic Curve equation, we know $a = 1$ and $b = 1$ Next, given a single point $P$, we can use the equations (16) to determine the slope $m$ That is, $m = \Large{\frac{3.0^2 + 1}{2.1}}\normalsize{\: (mod \: 5)}$ $= \Large{\frac{1}{2}}\normalsize{\: (mod \: 5)} = 2^{-1} \: (mod \: 5)$ $= 3$ To find $5P$, we need to find $2P$ and $4P$ to get to $5P = 4P + P$ Since we know the slope $m$ and the x-coordinate for the point $P$, we can use the equation (17) to find the x-coordinate for the point $2P = P + P$ That is, $x_3 = [m^2 - 2.x] \: (mod \: 5) = [3^2 - 2.0 = 9] \: (mod \: 5) = 4$ Now that we know the x-coordinate for the point $2P = P + P$, we can use the equation (15) to find the y-coordinate for the point $2P = P + P$ That is, $y_3 = [m.(x_1 - x_3) - y_1] \: (mod \: 5) = [3.(0 - 4) - 1] \: (mod \: 5) = [3.(-4) - 1] \: (mod \: 5) = -13 \: (mod \: 5) = 2$ Therefore, $2P = P + P = (4, 2)$ The slope for the line $4P$ will be, $m = \Large{\frac{3.4^2 + 1}{2.2}}\normalsize{\: (mod \: 5)}$ $= \Large{\frac{ 49}{4}}\normalsize{\: (mod \: 5)} = [49 \: (mod \: 5) . 4^{-1} \: (mod \: 5)] \: (mod \: 5) = (4.4) \: (mod \: 5) = 1$ The x-coordinate for the point $4P$ is, $x_3 = [m^2 - 2.x] \: (mod \: 5) = [1^2 - 2.4 = -7] \: (mod \: 5) = 3$ The y-coordinate for the point $4P$ is, $y_3 = [m.(x_1 - x_3) - y_1] \: (mod \: 5) = [1.(4 - 3) - 2] \: (mod \: 5) = [1 - 2] \: (mod \: 5) = -1 \: (mod \: 5) = 4$ Therefore, $4P = 2P + 2P = (3, 4)$ To find $5P = P + 4P$, we will use the points $P = (0, 1)$ and $4P = (3, 4)$ Next, given the two points, we can use the equations (13) to determine the slope $m$ That is, $m = \Large{\frac{4 - 1}{3 - 0}}\normalsize{\: (mod \: 5)}$ $= \Large{\frac{3}{3}}\normalsize{\: (mod \: 5)}$ $= 1 \: (mod \: 5) = 1$ Since we know the slope $m$ and the x-coordinates for the two points, we can use the equation (14) to find the x-coordinate for the point $5P$ over $\mathbb{F}_5$ That is, $x_3 = [m^2 - x_1 - x_2] \: (mod \: 5) = [1^2 - 0 - 3 = -2] \: (mod \: 5) = 3$ Now that we know the x-coordinate for the point $5P$, we can use the equation (15) to find the y-coordinate for the point $5P$ over $\mathbb{F}_5$ That is, $y_3 = [m.(x_1 - x_3) - y_1] \: (mod \: 5) = [1.(0 - 3) - 1] \: (mod \: 5) = [1.(-3) - 1] \: (mod \: 5) = -4 \: (mod \: 5) = 1$ Therefore, $5P = (3, 1)$ over $\mathbb{F}_5$

Example-4

Given the Elliptic Curve $y^2 = x^3 + x + 1$ over $\mathbb{F}_5$ along with a point $P = (0, 1)$, find the point for $5P$ over $\mathbb{F}_5$

From the given Elliptic Curve equation, we know $a = 1$ and $b = 1$

Next, given a single point $P$, we can use the equations (16) to determine the slope $m$

That is, $m = \Large{\frac{3.0^2 + 1}{2.1}}\normalsize{\: (mod \: 5)}$ $= \Large{\frac{1}{2}}\normalsize{\: (mod \: 5)} = 2^{-1} \: (mod \: 5)$ $= 3$

To find $5P$, we need to find $2P$ and $4P$ to get to $5P = 4P + P$

Since we know the slope $m$ and the x-coordinate for the point $P$, we can use the equation (17) to find the x-coordinate for the point $2P = P + P$

That is, $x_3 = [m^2 - 2.x] \: (mod \: 5) = [3^2 - 2.0 = 9] \: (mod \: 5) = 4$

Now that we know the x-coordinate for the point $2P = P + P$, we can use the equation (15) to find the y-coordinate for the point $2P = P + P$

That is, $y_3 = [m.(x_1 - x_3) - y_1] \: (mod \: 5) = [3.(0 - 4) - 1] \: (mod \: 5) = [3.(-4) - 1] \: (mod \: 5) = -13 \: (mod \: 5) = 2$

Therefore, $2P = P + P = (4, 2)$

The slope for the line $4P$ will be, $m = \Large{\frac{3.4^2 + 1}{2.2}}\normalsize{\: (mod \: 5)}$ $= \Large{\frac{ 49}{4}}\normalsize{\: (mod \: 5)} = [49 \: (mod \: 5) . 4^{-1} \: (mod \: 5)] \: (mod \: 5) = (4.4) \: (mod \: 5) = 1$

The x-coordinate for the point $4P$ is, $x_3 = [m^2 - 2.x] \: (mod \: 5) = [1^2 - 2.4 = -7] \: (mod \: 5) = 3$

The y-coordinate for the point $4P$ is, $y_3 = [m.(x_1 - x_3) - y_1] \: (mod \: 5) = [1.(4 - 3) - 2] \: (mod \: 5) = [1 - 2] \: (mod \: 5) = -1 \: (mod \: 5) = 4$

Therefore, $4P = 2P + 2P = (3, 4)$

To find $5P = P + 4P$, we will use the points $P = (0, 1)$ and $4P = (3, 4)$

Next, given the two points, we can use the equations (13) to determine the slope $m$

That is, $m = \Large{\frac{4 - 1}{3 - 0}}\normalsize{\: (mod \: 5)}$ $= \Large{\frac{3}{3}}\normalsize{\: (mod \: 5)}$ $= 1 \: (mod \: 5) = 1$

Since we know the slope $m$ and the x-coordinates for the two points, we can use the equation (14) to find the x-coordinate for the point $5P$ over $\mathbb{F}_5$

That is, $x_3 = [m^2 - x_1 - x_2] \: (mod \: 5) = [1^2 - 0 - 3 = -2] \: (mod \: 5) = 3$

Now that we know the x-coordinate for the point $5P$, we can use the equation (15) to find the y-coordinate for the point $5P$ over $\mathbb{F}_5$

That is, $y_3 = [m.(x_1 - x_3) - y_1] \: (mod \: 5) = [1.(0 - 3) - 1] \: (mod \: 5) = [1.(-3) - 1] \: (mod \: 5) = -4 \: (mod \: 5) = 1$

Therefore, $5P = (3, 1)$ over $\mathbb{F}_5$

Use of Elliptic Curves

Elliptic Curves find their value in Cryptography. The Elliptic Curve Cryptography is a very popular and commonly used modern public-private key cryptography standard that uses the Elliptic Curves over $\mathbb{F}_p$, where $p$ is an odd prime number.

Discrete Logarithm Problem

Let $a$, $b$, and $k$ all be integers from a finite field $\mathbb{F}_p$, where $p$ is an odd prime integer. Now, assume that there exists an integer $k \in \mathbb{F}_p$ such that the following equation is true:

$a^k \equiv b \: (mod \: p)$

If we know $a$ and $k$, it is very easy to find $b$. But, on the other hand, if we only know $a$ and $b$, it is extremely hard to find $k$. This is the crux of the Discrete Logarithm Problem.

For the Elliptic Curve Cryptography, the Discrete Logarithm Problem changes as follows:

$k.P = Q$, where $\set{k, P, Q} \in \mathbb{F}_p$

In other words, given the two points $P$ and $Q$, it is very difficult to find $k$.

This is the reason why Elliptic Curves play a major role in Cryptography.

Diffie-Hellman Key Exchange Algorithm

If $E(\mathbb{F}_p)$ is the given Elliptic Curve over $\mathbb{F}_p$ with $p$ being an odd prime, the following is the high-level algorithm for the key exchange:

Alice and Bob agree on a point $P$ in $E(\mathbb{F}_p)$ as the base point
Alice chooses a private key $a$ and then computes the point $Q = a.P \in E(\mathbb{F}_p)$
Alice shares the point $Q$ with Bob
Bob chooses a private key $b$ and then computes the point $R = b.P \in E(\mathbb{F}_p)$
Bob shares the point $R$ with Alice
Alice computes the shared key $a.R = a.(b.P) = a.b.P \in E(\mathbb{F}_p)$
Bob computes the shared key $b.Q = b.(a.P) = a.b.P \in E(\mathbb{F}_p)$
Alice and Bob can now securely communicate using the shared key $a.b.P \in E(\mathbb{F}_p)$

Elliptic Curve Cryptography (ECC) Algorithm

If $E(\mathbb{F}_p)$ is the given Elliptic Curve over $\mathbb{F}_p$ with $p$ being an odd prime, the following is the high-level algorithm for ECC:

Alice chooses a point $P$ in $E(\mathbb{F}_p)$ as a public point
Alice chooses a private key $a$ and then computes the point $Q = a.P \in E(\mathbb{F}_p)$
Alice shares the set $\set{\mathbb{F}_p, E(\mathbb{F}_p), P, Q}$ as the public key
Bob chooses a private key $b$ and then computes the point $R = b.P \in E(\mathbb{F}_p)$
Bob shares the set $\set{\mathbb{F}_p, E(\mathbb{F}_p), P, R}$ as the public key
Alice wishes to send a confidential message $m$ to Bob, which is encoded as a point $M$ on $E(\mathbb{F}_p)$
Alice encrypts the point $M$ on $E(\mathbb{F}_p)$ as $X = M + a.R = M + a.(b.P) = M + a.b.P$ and sends it to Bob
Bob decrypts the point $X$ on $E(\mathbb{F}_p)$ as $M = X + (-b.Q) = X + [-b.(a.P)] = X + (-a.b.P)$

References

Elliptic Curve Visual Tool

Multiplicative Inverse Calculator