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 + a1xy + a3y = x^3 + a2x^2 + a4x + a6, ai\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₁⊞P₂.
• ∞ 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₁⊞P₂ for the elliptical curbes (E/F_pⁿ) over the finite fields (F_pⁿ). 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=pⁿ, ⊞) 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_pⁿ, ⊞), this if our coefficients a, b and c are still the same.

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

• ε₁ = (p + 1) - #(E/F_p, ⊞) and ε₀ = 2
• ε_n = ε₁ε_{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₆₅₅₃₆

What do we know:

• We know that by applying F_{q = pⁿ} that F_{65536 = 2¹⁶}, so q = 65536, p = 2 and n = 16.
• The number of points for when n = 1 and p = 2 is 4 (this is given).
• ε₀ = 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 ε₁ 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₃₇, ⊞) |ε| ≤ 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² = x³ + ax + b, we know that this is a (E/F_3ⁿ, ⊞) 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² = x³ ⊕ a⊗x ⊕ b (Note: the power is also multiplicative!).

1.3.1 Formulas

2P = ∞

1. z = (3⊗x² ⊕ a) ⊘ (2⊗y)
2. 2P ≡ (x”,y”)
3. x” = z² ⊖ 2⊗x
4. y” = z ⊗(x ⊖ x”) ⊖ y

We can now calculate (x₃, y₃) = (x₁, y₁) ⊞ (x₁, y₁)

1. z = (y₂ ⊖ y₁) ⊘ (x₂ ⊖ x₁)
2. x3 = z² ⊖ x₁ ⊖ x₂
3. y3 = z ⊗ (x₁ ⊖ x₃) ⊖ y₁

1.3.2 Example

Question: We have (E/F₅), a=4, b=1, n=1 (so we have modulo 5) and E: y² = x³ + ax + b

We know that E: y² = x³ + ax + b = E: y² = x³ + 4x + 1

We can calculate x³ + 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³ + 4x + 1 | | 0³ + 4 * 0 + 1 mod 5 = 1 | 1³ + 4 * 1 + 1 mod 5 = 1 | 2³ + 4 * 2 + 1 mod 5 = 2 | 3³ + 4 * 3 + 1 mod 5 = 0 | 4³ + 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³ + 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_2ⁿ

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 = ∞

1. z = x ⊕ (y ⊘ x)
2. 2P ≡ (x”,y”)
3. x” = z² ⊕ z ⊕ a
4. y” = x² ⊕ (z ⊗ x'') ⊕ x''

We can now calculate (x₃, y₃) = (x₁, y₁) ⊞ (x₁, y₁)

1. z = (y₁ ⊕ y₂) ⊘ (x₁ ⊕ x₂)
2. x3 = z² ⊕ z ⊕ x₁ ⊕ x₂ ⊕ a
3. y3 = z ⊗ (x₁ ⊕ x₃) ⊕ x₃ ⊕ y₁

1.4.2 Example

Question: We have (E/F_2³), a=1, b=element 2, n is NOT equal to 1

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

Note: We are using the additive table here for the field F_2³

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

| | | | | | | | | | |:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:| | x | 0 | 1 | 2 | 3 | 4 | 5 | 6 | ∞ | x³ | 0 | 3 | 6 | 2 | 5 | 1 | 4 | ∞ | 0 ⊗ x² | 0 | 2 | 4 | 6 | 1 | 3 | 5 | ∞ | x³ ⊕ 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=pⁿ, ⊞) is cyclical
• μ(#E)=0, then we need to check this, check the methods 1.3 and 1.4 for this.