# Fields - Elliptical Curves Over Finite Fields

## 1.1 Weierstrass Equations

### 1.1.1 Introduction

A weierstrass equation is an elliptical curve with a collection of points (x, y) (xεF and yεF) and is of the third grade with the form:

$$ y^2 + a*1xy + a*3y = x^3 + a*2x^2 + a*4x + a*6, a*i\epsilon F $$

and ∞ always added as a point.

### 1.1.2 Notions

- We have an interaction ⊞ or + that converts (E/F, ⊞) to an abelian group (see groups). We can create formulas to interpret P
_{1}⊞P_{2}. - ∞ is the neutral element
- The inverse of P is -P or P' (Noted as P⊞P'=∞)
- P n times itself is written as nP (Example: 2P is the doubling of the point P)

We will create formulas for P_{1}⊞P_{2} for the elliptical curbes (E/F_{pn}) over the finite fields (F_{pn}). Which allows us to reduce the amount of Weirstrass equations to 5 cases:

**Supersingular Cases**

- $(E/F_{2n}, ⊞), E: y^2 + cy = x^3 + ax + b$
- $(E/F_{3n}, ⊞), E: y^2 = x^3 + ax + b$

**Not-Supersingular Cases**

- $(E/F_{2n}, ⊞), E: y^2 + xy = x^3 + ax^2 + b$
- $(E/F_{3n}, ⊞), E: y^2 = x^3 + ax^2 + b$

**Over fields with characteristic p ≥ 5**

- $(E/F_{p^n}, ⊞), E: y^2 = x^3 + ax + b$

## 1.2 Number of points

The number of points (#E) on a elliptical curbe (E/F_{q=pn}, ⊞) depends on the coefficients (a, b, c) in the equations from our previous point.

To get #E we need to know the number of points for #(E/F_{p}, ⊞), if we know this we can get the number of points for #(E/F_{pn}, ⊞), this if our coefficients a, b and c are still the same.

Once we know this we can create a recursion equation for #E:

- ε
_{1}= (p + 1) - #(E/F_{p}, ⊞) and ε_{0}= 2 - ε
_{n}= ε_{1}ε_{n - 1}- pε_{n - 2}

**Example:** Coefficients are: a = 0, b = 1 and $(E/F_2, ⊞) = {(1,0), (0,1), (1,1), (∞, ∞)}$. Calculate the number of points for F_{65536}

What do we know:

- We know that by applying F
_{q = pn}that F_{65536 = 216}, so q = 65536, p = 2 and n = 16. - The number of points for when n = 1 and p = 2 is 4 (this is given).
- ε
_{0}= 2

We can fill this into a table already. If we do this we get:

| q | | 2 | 4 | 8 | 16 | 32 | 64 | 128 | 256 | 512 | 1024 | 2048 | 4096 | 8192 | 16384 | 32768 | 65536 |:-:||:-:||:-:||:-:||:-:||:-:||:-:||:-:||:-:||:-:||:-:||:-:||:-:||:-:||:-:||:-:||:-:||:-:| | **ε** | 2 | **#E** | |

If we now apply the 2 formulas for ε_{1} and ε_{n} we get:

| q | | 2 | 4 | 8 | 16 | 32 | 64 | 128 | 256 | 512 | 1024 | 2048 | 4096 | 8192 | 16384 | 32768 | 65536 |:-:||:-:||:-:||:-:||:-:||:-:||:-:||:-:||:-:||:-:||:-:||:-:||:-:||:-:||:-:||:-:||:-:||:-:| | **ε** | 2 | -1 | -3 | 5 | 1 | -11 | 9 | 13 | -31 | 5 | 57 | -67 | -47 | 181 | -87 | -275 | 449 | **#E** | | 4 | 8 | 4 | 16 | 44 | 56 | 116 | 288 | 508 | 968 | 2116 | 4144 | 8012 | 16472 | 33044| 65088

> Note: We can check find out the range the points lie in by checking the Hasse Interval, you do this by saying ε = (q + 1) - #E, then |ε| is always smaller or equal to 2√q. (Example: for (E/F_{37}, ⊞) |ε| ≤ 12 ==> 26 ≤ #E ≤ 50)

## 1.3 Curves over Characteristic (F) ≥ 5

Let's say we got a Weirstrass Equation that is of the form: **E: y ^{2} = x^{3} + ax + b**, we know that this is a (E/F

_{3n}, ⊞) Supersingular equation. Because we are working with fields, we can write the + and the * as the additive and multiplicative interactions between the elements. Now we get:

**E: y**(Note: the power is also multiplicative!).

^{2}= x^{3}⊕ a⊗x ⊕ b### 1.3.1 Formulas

2P = ∞

- z = (3⊗x
^{2}⊕ a) ⊘ (2⊗y) - 2P ≡ (x”,y”)
- x” = z
^{2}⊖ 2⊗x - y” = z ⊗(x ⊖ x”) ⊖ y

We can now calculate (x_{3}, y_{3}) = (x_{1}, y_{1}) ⊞ (x_{1}, y_{1})

- z = (y
_{2}⊖ y_{1}) ⊘ (x_{2}⊖ x_{1}) - x3 = z
^{2}⊖ x_{1}⊖ x_{2} - y3 = z ⊗ (x
_{1}⊖ x_{3}) ⊖ y_{1}

### 1.3.2 Example

**Question: We have (E/F _{5}), a=4, b=1, n=1 (so we have modulo 5) and E: y^{2} = x^{3} + ax + b**

We know that E: y^{2} = x^{3} + ax + b = E: y^{2} = x^{3} + 4x + 1

We can calculate x^{3} + 4x + 1 by executing the equation on the X'es given, and y by taking the root from the right side of our equation, do note that this can be non existant (if the root can't be taken). Another way to calculate y would be to check where y * y in our multiplication table is equal to our right side of the equation.

So if we put this into a table to calculate the points:

| Calculations | | - | | Calculating x^{3} + 4x + 1 | | **0**^{3} + 4 * **0** + 1 mod 5 = 1 | **1**^{3} + 4 * **1** + 1 mod 5 = 1 | **2**^{3} + 4 * **2** + 1 mod 5 = 2 | **3**^{3} + 4 * **3** + 1 mod 5 = 0 | **4**^{3} + 4 * **4** + 1 mod 5 = 1 | **Calculating y**| | sqrt(1) = 1 | | sqrt(1) = 1 | | sqrt(2) = / | | sqrt(0) = 0 | | sqrt(1) = 1 | | **Calculating y'** | | 1' = 4 | | 1' = 4 | | /' = / | | 0' = / | | 1' = 4 |

Putting it into a simple table:

| Formula | | | | | | | :-: | :-: | :-: | :-: | :-: | :-: | | **----------------** | **----** | **----** | **----** | **----** | **----** | | **x** | 0 | 1 | 2 | 3 | 4 | **x ^{3} + 4x + 1** | 1 | 1 | 2 | 0 | 1 |

**----------------**|

**----**|

**----**|

**----**|

**----**|

**----**| |

**y**| 1 | 1 | | 0 | 1 |

**y'**| 4 | 4 | | 4

Out of this table we can read that our points are:

- #E = 8
**A(4, 1)**and**A'(4, 4)****B(1, 1)**and**B'(1, 4)****C(0, 4)**and**C'(0, 1)****O(3, 0) = O' --> O ⊞ O' = ∞**

Now we can apply everything that we calculated on the formulas in point 1.3.1 and we can get the 2P, or the doubling of our point P

P | x | y | 2y | (2y)' | z | x'' | y'' | 2P :-: |:-: |:-: |:-: |:-: |:-: |:-: |:-: |:-: | A | 4 | 1 | 2 | 3 | 1 | 3 | 0 | O A' | 4 | 4 | 3 | 2 | 4 | 3 | 0 | O B | 1 | 1 | 2 | 3 | 1 | 4 | 1 | A B' | 1 | 4 | 3 | 2 | 4 | 4 | 4 | A' C | 0 | 4 | 3 | 2 | 3 | 4 | 4 | A' C' | 0 | 1 | 2 | 3 | 2 | 4 | 1 | A'

and last but not least, we can fill in the group table.

| | | ∞ | A | O | A' | B | C | C' | B' | :-: | :-: | :-: | :-: | :-: | :-: | :-: | :-: | :-: | | | **∞** | ∞ | A | O | A' | B | C | C' | B' | **(4,1)** | **A** | A | O | | ∞ | | | | | **(3,0)** | **O** | O | | ∞ | | | | | | **(4,4)** | **A'** | A' | ∞ | | O | | | | | **(1,1)** | **B** | B | | | | A | | | ∞ | **(0,4)** | **C** | C | | | | | A' | ∞ | | **(0,1)** | **C'** | C' | | | | | ∞ | A | | **(1,4)** | **B'** | B' | | | | ∞ | | | A'

## 1.4 Not-supersingular curves E/F_{2n}

By applying the same method as in point 1.3 we will be able to do this for the not supersingular curves.

Only this time we have different formulas:

### 1.4.1 Formulas

2P = ∞

- z = x ⊕ (y ⊘ x)
- 2P ≡ (x”,y”)
- x” = z
^{2}⊕ z ⊕ a - y” = x
^{2}⊕ (z ⊗ x'') ⊕ x''

We can now calculate (x_{3}, y_{3}) = (x_{1}, y_{1}) ⊞ (x_{1}, y_{1})

- z = (y
_{1}⊕ y_{2}) ⊘ (x_{1}⊕ x_{2}) - x3 = z
^{2}⊕ z ⊕ x_{1}⊕ x_{2}⊕ a - y3 = z ⊗ (x
_{1}⊕ x_{3}) ⊕ x_{3}⊕ y_{1}

### 1.4.2 Example

**Question: We have (E/F _{23}), a=1, b=element 2, n is NOT equal to 1**

We can now calculate the points by E: y ⊗ (x ⊕ y) = x^{3} ⊕ element 0 ⊗ x2 ⊕ element 2

Note: We are using the additive table here for the field F_{23}

After solving this like we did in 1.3, we get the following result:

| | | | | | | | | | |:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:| | **x** | 0 | 1 | 2 | 3 | 4 | 5 | 6 | ∞ | **x ^{3}** | 0 | 3 | 6 | 2 | 5 | 1 | 4 | ∞ |

**0 ⊗ x**| 0 | 2 | 4 | 6 | 1 | 3 | 5 | ∞ |

^{2}**x**| 2 | 3 | 5 | 6 | 0 | 6 | 6 | 2 |

^{3}⊕ 0 ⊗ x2 ⊕ 2**y**| 4 | 0 | 1 | | | | 1 | 1 |

**y'**| 5 | 3 | 4 | | | 5 |

#E = 10

And the points are:

**A(0,4)**and**A'(0,5)****B(6,1)**and**B'(6,5)****C(1,0)**and**C'(1,3)****D(2,1)**and**D'(2,4)****O(∞,1)=O' --> O ⊞ O' = ∞**

The same goes for the doubling of the points (2P), see 1.3 for this.

## 1.5 Cyclical group or not?

We can check if a group is cyclical by using the following methods:

- μ(#E)≠0, then (E/F
_{q=pn}, ⊞) is cyclical - μ(#E)=0, then we need to check this, check the methods 1.3 and 1.4 for this.