June 5, 2015 - discrete-math

# Fields - Elliptical Curves Over Finite Fields

Xavier Geerinck

## 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
_{pn}, ⊞), 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' | ||
---|---|---|---|---|---|---|---|---|

∞ | ∞ | A | O | A' | B | C | C' | |

(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' | ∞ |

## 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^{2} | 0 | 2 | 4 | 6 | 1 | 3 | 5 | ∞ | |

x^{3} ⊕ 0 ⊗ x2 ⊕ 2 | 2 | 3 | 5 | 6 | 0 | 6 | 6 | 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.