Solving a Sudoku is not an easy task, not for humans and even a computer can struggle with it if it has to go through each combination and try brute forcing the puzzle without any clue.

Lucky for us we are able to tackle this problem by using Discrete Math and treating the problem as a Exact Cover problem. This problem can be solved by creating a dual interpretation of our problem and solving it manually by using the algorithm X or by creating dancing links and programming this algorithm.

&gt; For the full details about this algorithm, please check out the paper by **Donald E. Knuth** from Stanford University. [http://lanl.arxiv.org/pdf/cs/0011047.pdf](http://lanl.arxiv.org/pdf/cs/0011047.pdf)

In this article I will explain on what a Dual Interpretation is, What the algorithm X is and how we can apply these to solve a 2 x 2 sudoku.

## Dual Interpretation

Our Dual Interpretation will take constraints and fulfilment of these constraints and put those into one table or matrix so that we can use these constraints and fulfilment's to construct a solution.

The best way to explain this is by showing an example.

Let's say we have a graph that looks like this:

![graph](https://drive.google.com/uc?export=view&amp;id=0B-cbbSwiSpTPTjA3NHk5U3BFYlU)

Here we can see that we got connections between the points on the top and the points on the bottom. For our dual interpretation we will say that the top values are our constraints, and the bottom ones are our fulfilment's for these constraints. We then create a table with our constraints as the columns and the fulfilment's as the X values. The result looks like this:

![dual_interpretation_graph](https://drive.google.com/uc?export=view&amp;id=0B-cbbSwiSpTPb1BPdmd4VUdJTjQ)

This is our Dual Interpretation for this specific graph. We will need this to construct a unique solution that will connect each node from the top with one of the bottom without multiple connections, for this we are going to use the Algorithm X.

## Algorithm X

The Algorithm X is a name given by Donald E. Knuth to an algorithm that is able to determine the solution to specific problems based on our Dual Interpretation. Popular problems being solved with this algorithm are: Pentomino's, Sudoku's and The n*n Queen Problem.

The algorithm works like this:

1. Pick a fulfilment from our dual interpretation, then mark all the cells in this row. (Add this row to a new table called solution)
2. Select every cel in the columns that contain a marked cell from step 1.
3. Remove all the rows that have a marked cell.
4. After removal, we need to check if the removal worked and we can still find a unique solution!
1. If there are no MARKED columns anymore, but there is still an empty column, then there is a fulfilment that has disappeared and we need to reverse everything till step 1 and pick another fulfilment to start with.
2. If we have no MARKED columns and no EMPTY columns, then we are clear to proceed to step 5.
5. Iterate again starting from step 1 until we have fulfilled every fulfilment.

We will now apply this algorithm on the Dual Interpretation created in the previous chapter.

![algorithm_x](https://drive.google.com/uc?export=view&amp;id=0B-cbbSwiSpTPNW5YbDdnVUppYms)

We now know the basics to start solving a 2 x 2 sudoku.

## Applying the learned techniques on a 2 x 2 Sudoku

### Creating the dual interpretation

I will start by explaining this technique on a 2 x 2 sudoku, the reason for this will be clear after our first part ;)

The concept of a sudoku is pretty straightforward, you fill in a number from 1 to n and make sure this number does not appear horizontally, vertically and in the same block, or partitions. Many of us will also think the sudoku as a Latin Square, this is a square with the order n where every number appears exactly once in each row and column.

If we solve a 2 x 2 "Latin Square" or "Sudoku" then we get this as one of the solutions:

| 1 | 2 |
| :-: | :-: |
| **2** | **1** |

To achieve this with our algorithm X we will first have to create the Dual Interpretation, we can do this by finding the constraints and filling the fulfilment's for these constraints.

Our constraints for a sudoku this size are:

- 2 x 2 cell constraint (every cell has a number)
- 2 x 2 row constraint (every row has each number once)
- 2 x 2 column constraint (every column has each number once)

This means that we will have 23 = 8 fulfilment's (or facts) (where 3 is the number of different constraints and 2 is our n) and 2\*2 + 2\*2 + 2\*2 = 12 constraints.

We can now get started creating our table that will hold our fulfilment's and constraints, we chose the X values (or the rows) as our positions where a number can be placed (and this for each number). And our Y values (the columns) for each constraint group.

Constraint groups:

1. A number is in row X and column Y
2. Number A is in row X
3. Number A is in column Y

So our heading (columns) will look like this:

![2x2sudoku](https://drive.google.com/uc?export=view&amp;id=0B-cbbSwiSpTPUUxEVE15ek5Rcmc)

Now we create the legend for our rows, this makes us able to identify the solution on the end. Here we choose the value we put into the cell at row x and column y:

![2x2sudoku](https://drive.google.com/uc?export=view&amp;id=0B-cbbSwiSpTPaGRIbXpVeFVUVUU)

Now we just have to fill in our own constraints and we will get this:

![2x2sudoku](https://drive.google.com/uc?export=view&amp;id=0B-cbbSwiSpTPeHJ3VVdPVEVfUlU)

Once we have that we are finally able to solve our sudoku by applying the Algorithm X algorithm.

### Finding the solution by applying algorithm X

There is nothing hard about this step, we just perform algorithm X again as explained before and we will get this solution:

![2x2sudoku_solution](https://drive.google.com/uc?export=view&amp;id=0B-cbbSwiSpTPTjhBMWtjcWQ0c0U)

We now have our solution for this sudoku puzzle.

## Conclusion

When understanding the problem correctly, we are able to solve problems such as the sudoku problem in a very short time frame. The hardest part about this is most likely getting our constraints correct and creating the dual interpretation, but once this is done we have the solution in no time.

In this example we saw the Algorithm X applied on a 2 x 2 sudoku puzzle, but this is in fact possible on every other sudoku puzzle out there, the only thing we will need to add is a region constraint (Number A is in region Z).

As always, feel free to ask questions if you are stuck, or think I could improve something.

Solving a Sudoku with Discrete Math


This post is about the discrete math that is being taught at the University Ghent for people attending the Bridge program to Master Of Science in Industrial Engineering (IT).

In this program we learned about 3 specific sub-groups of Discrete Mathematics:

* Fields
* Graphs
* Groups

In this post I will summarise the most important exercises that we learned and I will explain on how to solve them.

## 1.0 Fields
A field is a collection of elements that interact with each other through interaction by ⊕ or ⊖. These 2 symbols stand for additive and multiplicative interactions.

Field Axioms:

* (F, ⊕) : Additive group, with neutral element ⦶ (the zero element)
* (F\\⦶, ⊖) : Multiplicative group with neutral element 1 (base element)

We can create those finite fields with 1 of the 2 methods:

### 1.1 Prime Fields
__Prime Fields (ℤp,+,.):__ ) Creates a field with the zero element __0__ and the base element __1__, but __p__ has to be a prime number!

* __(ℤp\0,+,.)__ cyclic group __if__ p is prime
* __(ℤ12,+,.)__ not a field, because (ℤ12\0,.) is not a group

We can dissolve every integer as a product of powers of prime factors. Do note that we can do this by hand but that this gets harder for bigger numbers, that is why we mostly write programs to do this for us.

Prime numbers are used in many ways in Discrete Math, some of the problems we can solve using prime numbers are: calculating the Euler φ, Galois Field orders, … These examples will be shown later.

&gt; 1. __Prime Numbers:__ This are numbers that we can only divide by 1 and itself. (Example: 3, 1, 11, …)
&gt; 2. __Axioms:__ Is something that is not proven, but it is generally accepted.

### 1.1.2 Euclidean Algorithm
#### 1.1.2.1 Calculating the GCD (Greatest Common Divisor) and LCM (Least Common Multiple)
When we know the prime factors of the 2 given integers X and Y then it is easy to calculate the GCD and the LCM.

$$gcd(x, y) * lcm(x, y) = x * y$$

##### 1.1.2.1.1 GCD
The Greatest Common Divisor of 2 or more integers is found when we can divide the largest positive integer (both of the integers are &gt; 0) by the other numbers without a remainder. Example: GCD(8, 12) = 4

If the gcd(x, y) = 1 then the number is a __relative prime__.

When we apply this to our prime factors, then this means that we want to get the smallest exponents that appear in both X and Y.

__Example:__ Calculate the GCD of 792 and 2420.
1) Find the prime factors:
$$792 = 2 * 2 * 2 * 3 * 3 * 11 = 2^3 * 3^2 * 11$$
$$2420 = 2 * 2 * 5 * 11 * 11 = 2^2 * 5 * 11^2$$

2) Find the smallest exponents and numbers that appear in both the prime factors:
$$2^2*11$$

==&gt; This is your GCD

##### 1.1.2.1.2 LCM
The Least Common Multiple works the same was as the GCD, only do we now find the biggest exponents in the prime factors that appear in X and/or Y.

__Example:__ Calculate the LCM of 792 and 2420.
1) Find the prime factors:
$$792 = 2 * 2 * 2 * 3 * 3 * 11 = 2^3 * 3^2 * 11$$
$$2420 = 2 * 2 * 5 * 11 * 11 = 2^2 * 5 * 11^2$$

2) Find the biggest exponents in the numbers, and get all of them
$$2^3 * 3^2 * 5 * 11^2 = 43560$$

==&gt; This is your LCM

#### 1.1.2.2 Calculating the GCD and LCM with the Euclidian Algorithm
The Euclidian Algorithm can also be used to calculate the GCD and LCM. This algorithm works by performing a remainder division, after we did this we then get the gcd on the right bottom (if remainder = 0), or on the left bottom (if the remained &gt; 0).

__Example:__ 99 / 84 with the use of the euclidean algorithm.

X | | Y | Comment
- | - | -- | -------
99 | | |
84 | 1 | 84 |
- ---| | | (99 - 84) = 15
15 | 5 | 75 |
| |- ----| (84 - 75) = 9
9 | 1 | 9 |
- ---| | | (15 - 9) = 6
6 | 1 | 6 |
| |- ----| (9 - 6) = 3
6 | 2 | 3 |
- ---| | | (6 - 6) = 0
0 | | |

==&gt; Remainder is 0, so the right bottom is the GCD = 3

==&gt; Our LCM = (99 * 84) / 3 = 2772

__Example 2:__ calculate the LCM and the GCD of 792 and 2420 using the Euclidean Algorithm

==&gt; After performing the steps described above we get that GCD = 44

==&gt; LCM = (792 * 2420) / 44 = 43560

#### 1.1.2.3 The Extended Euclidean Algorithm
The extended Euclidean algorithm allows us to check our calculations and if our GCD(x, y) = 1, then the extended euclidean algorithm allows us to calculate (1 / x) % y efficiently.

__steps:__

1. Write out the basic algorithm
2. Add 3 columns to the right of the basic algorithm. In the center column write your result of the middle column of the basic algorithm. Now write 1 in the top left and 0 as the second number on the right. Now perform the basic algorithm with these numbers multiplying them with the numbers in the middle column. Keep doing this till you are on the same line as your last number in the middle column.
3. Do the same as step 2 but this time use 0 in the top left and 1 as the second number.

__Example:__ Find the gcd, lcm and the result for 53-1 % 97

__Step 1:__

![extended euclidean algorithm](https://drive.google.com/uc?export=view&amp;id=0B-cbbSwiSpTPTXZBZW4tUldvR0k)

__Step 2:__

![extended euclidean algorithm](https://drive.google.com/uc?export=view&amp;id=0B-cbbSwiSpTPYUh0OTFCTE1uZjg)

__Result:__

![extended euclidean algorithm](https://drive.google.com/uc?export=view&amp;id=0B-cbbSwiSpTPYi1rSEt4RU5Da2M)

Here we can see that the inverse of 53 modulo 97 is equal to 11.

#### 1.1.2.4 Chain Divisions
Chain divisions allow us to write square roots as big divisions so that they near this square root. This algorithm is also based on the Euclidean algorithm, but only a bit modified. So we will simplify it.

$$\sqrt[3]{10} \simeq \frac{105033}{48752} $$

To calculate this in a long division, we keep repeating these steps:

1. Get the number before the . (write this down)
2. Do our original number minus this number
3. Inverse the resulting number
4. Repeat from step 1

__Example:__ 10^(1/3)

Remainder | Result (of the inverse, first result is our square root!)
:-------: | :-----
| 2.154434690
2 | 6.475229108
6 | 2.10424821
2 | 9.592490815
9 | 1.687789876
1 | 1.453932421
1 | 2.202971088
2 | 4.926810069
4 | 1.078969719
1 | 12.66308162
… | …

and we can continue doing this till infinity. the more numbers we calculate, the closer we will get to the square root.

To get this into the form that we need to see our square root we now just have to write them as a division of (1 / next) + remained

For the root that we calculated above this will be (ending with a 1 / 1):

$$\frac{1}{\frac{1}{\frac{1}{\frac{1}{\frac{1}{\frac{1}{\frac{1}{\frac{1}{4\frac{1}{1} + 1} + } + 2} + 1} + 1} + 9} + 2} + 6} + 2$$

### 1.1.3 Multiplicative Functions
#### 1.1.3.1 The Euler φ
The Euler Phi will calculate how many numbers (for y &lt; x) the GCD = 1 Too calculate this we need to have the prime factoring, after we have the prime factor we can write the Euler Phi as the product of the fractions of the primes divided by the prime - 1 and afterwards multiplied by the number to calculate $$\varphi(n)=n\prod_{p|n}\left(1-\frac{1}{p}\right)$$ __Example: 1__ Euler Phi of 90 $$\varphi(90) = \varphi(2 * 3^2 * 5) = 90 * \frac{1}{2} * \frac{2}{3} * \frac{4}{5} = 24$$ __Example: 1__ Euler Phi of 21560 $$\varphi(21560) = \varphi(2^3 * 5 * 7^2 * 11) = 21560 * \frac{1}{2} * \frac{4}{5} * \frac{6}{7} * \frac{10}{11} = 6720$$ #### 1.1.3.2 Möbius μ ##### 1.1.3.2.1 Introduction The Möbius μ can have the numbers {-1, 0, 1} depending on the factorisation of the prime factors. μ(n) = 1 if n has an even amount of prime factors μ(n) = -1 if n has an odd amount of prime factors μ(n) = 0 if the number has a squared prime factor __Examples:__ μ(21) = μ(3 x 7) ==&gt; even number, so μ(21) = 1

μ(20) = μ(22 x 5) ==&gt; squared prime factor, so μ(20) = 0

μ(83) = μ(83) ==&gt; odd number, so μ(83) = -1

μ(30) = μ(2 x 3 x 5) ==&gt; odd, so μ(30) = -1

##### 1.1.3.2.2 Möbius Inversion
We can also use the μ function to calculate the Euler Phi, herefor we need to find all the dividors (d) first and then multiple them all together with the use of the Möbius function.

$$\varphi(90) = \mu(d) * \frac{x}{d}$$

__Example:__ Euler Phi of 90 With Möbius

$$\varphi(90) = 1, 2, 3, 5, 6, 10, 15, 30 = \mu(1) * \frac{90}{1} + \mu(2) * \frac{90}{2} + \mu(3) * \frac{90}{3} + \mu(5) * \frac{90}{5} + \mu(6) * \frac{90}{6} + \mu(10) * \frac{90}{10} +\mu(15) * \frac{90}{15} + \mu(30) * \frac{90}{30} = 24$$

#### 1.1.3.3 Legendre Symbol
The Legendre Symbol (x|p), also has {1, -1, 0} as a result.

$$
\left(\frac{x}{p}\right) =
\begin{cases}
1 &amp; \text{ if } x \text{ is a quadratic residue modulo } p \text{ and } x \not\equiv 0\pmod{p} \\ \newline
-1 &amp; \text{ if } x \text{ is a quadratic non-residue modulo } p \\ \newline
0 &amp; \text{ if } x \equiv 0 \pmod{p}.
\end{cases}
$$

### 1.1.4 Primitive Roots (modulo n)
Every integer a where the order modulo n is equal to φ(n) is a primitive root modulo n. If this is true, then a is a generator of the multiplicative group (ℤp\0,.).

This group of a prime field has exactly φ(p - 1) primitive roots

If we take p as a prime, then b is a primitive root for p if the powers of b (1, b, b2, n3, …) include all of the residue classes modulo p (except 0).

Imagine that we need to find the primitive root for 601, then we need to try 601 numbers to see if we get them all, this would be a lot of work but luckily we can test this faster.

A general method of testing if we got a primitive root is to check x to the power of every divisor of (p - 1) (modulo p). If only the last number results into 1, then this is a primitive root. Else it is not.

To find all those divisors, you just have to find the prime factorization of (p - 1) and then let those numbers interact with each other.

__Example 1:__ Primitive root of p = 7
If p = 7, 3 is a primitive root for p, because the powers of 3 are: 1, 3, 2, 6, 4, 5 (It generates every number for the prime except the prime itself and 0).

__Example 2:__ Primitive root of p = 7
If p = 7, then 2 is NOT a primitive root for p, because the powers of 2 are: 1, 2, 4, 1, 2, 4, 1, 2, 4, … which is missing the values 3, 5 and 6.

__Example 3:__ Primitive root of p = 601
Prime factors: 23, 3, 52
Factors:

$$
\begin{array}{lcr}
x &amp; x^3 &amp; x^5 &amp; x^{25} &amp; x^{3 * 25} &amp; x^{3 * 5} \newline
x^2 &amp; x^{2 * 3} &amp; x^{2 * 5} &amp; x^{2 * 25} &amp; x^{3 * 2 * 25} &amp; x^{3 * 5 * 2} \newline
x^4 &amp; x^{4 * 3} &amp; x^{4 * 5} &amp; x^{4 * 25} &amp; x^{3 * 4 * 25} &amp; x^{3 * 5 * 4} \newline
x^8 &amp; x^{8 * 3} &amp; x^{8 * 5} &amp; x^{8 * 25} &amp; x^{3 * 8 * 25} &amp; x^{3 * 5 * 8} \newline
\end{array}
$$

Now we just need to let x vary from 1 -&gt; 600 and increment by 1. And as soon as we get a 1 as the last number (last number = p - 1), then we got a primitive root.

![primitive_root_7](https://drive.google.com/uc?export=view&amp;id=0B-cbbSwiSpTPeGVTa2ZDLWMzcms)

__Conclusion:__ Here we find that for **x = 7** we get 1, which means that this is a primitive root.

&gt; Excel will not be able to solve this completely due to the upper limit being placed on the modulo function. More info here: [http://support.microsoft.com/kb/119083](http://support.microsoft.com/kb/119083)

### 1.1.5 Discrete Logarithms
A discrete logarithm will allow you to solve the equation:
$$
\newcommand{\Mod}[1]{\ (\text{mod}\ #1)}
ω^k \Mod{p} = x
$$

where ω and x are elements of a finite group.

#### Naive method
When we are given a prime (p), a primitive root (ω) and the result of ωk % p (x) then we can calculate the integer k by iterating over the group by using this formula:

$$
\newcommand{\Mod}[1]{\ (\text{mod}\ #1)}
\sum_{k=1}^{p - 1} ω^{k} \Mod{p}
$$

We call this the naive method because who wants to loop through every element for a primitive root? (image having to do this for the prime number 9973, then we would need to go through 9973 indexes). That is why we have a great algorithm for this, called the baby-step giant-step method.

#### The baby-step giant-step method
You will be able to perform this method for p &lt; 1040 which is fine for us in these exercises. (else search after the Polhlig-Hellman method).

To perform this algorithm, we have to follow these steps:

1. Calculate the first row, the number of elements in the row = square root prime, the element = ωk % p
2. Find the inverse value for the last value in the row that we calculated.
3. Create a column that starts with the index k given, then calculate the following elements in that column by doing the previous value * inverse value % p.
4. Repeat step 3 till we encounter a value that also appears in the row that we calculated, this value is the one we need.

__Example:__ Calculate the index of 4 for : ω = 5 in ℤ97

From this question we can derive that k = 4, ω = 5 and p = 97

Now we calculate our first row till the square root of 97 (which is 10 rounded, so we need 10 values)

![grand_step_baby_step](https://drive.google.com/uc?export=view&amp;id=0B-cbbSwiSpTPUFlsTXh2dlpPNjA)

Fields - Prime Fields

# 1 Galois Fields

## 1.1 Construction of Galois Fields

A Galois field has a finite amount of numbers and is written as GF(q) or Fq. Where q = pn.

When knowing all this we can now construct a Galois Field with n dimensions and p elements.

**Example:**

When we want to construct the galois field of F49 then we know that p = 7 and n = 2. Which means that we have 2 dimensions and 7 elements (elements ranging from 0 to 6). So to construct this we will need a grid the exists out of pn elements. Like this:

$$
\begin{matrix}
(0,0) &amp; (1,0) &amp; (2,0) &amp; (3,0) &amp; (4,0) &amp; (5,0) &amp; (6,0) \newline
(0,1) &amp; (1,1) &amp; (2,1) &amp; (3,1) &amp; (4,1) &amp; (5,1) &amp; (6,1) \newline
(0,2) &amp; (1,2) &amp; (2,2) &amp; (3,2) &amp; (4,2) &amp; (5,2) &amp; (6,2) \newline
(0,3) &amp; (1,3) &amp; (2,3) &amp; (3,3) &amp; (4,3) &amp; (5,3) &amp; (6,3) \newline
(0,4) &amp; (1,4) &amp; (2,4) &amp; (3,4) &amp; (4,4) &amp; (5,4) &amp; (6,4) \newline
(0,5) &amp; (1,5) &amp; (2,5) &amp; (3,5) &amp; (4,5) &amp; (5,5) &amp; (6,5) \newline
(0,6) &amp; (1,6) &amp; (2,6) &amp; (3,6) &amp; (4,6) &amp; (5,6) &amp; (6,6) \newline
\end{matrix}
$$

Of course, when n &gt; 2 then we are not able to write this as a grid, but we do now the elements that are in our field.

Now because our field construction is defined as (Fq, ⊕, ⊗) we need to have an additive interaction and a multiplicative interaction.

Our additive interaction is being done by executing the additive operations **mod p** for every dimension.

The multiplicative interaction needs to have a polynomial at every grid point with grade &lt; n

If we apply this on our field that we calculated then we get:

$$
\begin{matrix}
0 &amp; x &amp; 2x &amp; 3x &amp; 4x &amp; 5x &amp; 6x \newline
1 &amp; x+1 &amp; 2x+1 &amp; 3x+1 &amp; 4x+1 &amp; 5x+1 &amp; 6x+1 \newline
2 &amp; x+2 &amp; 2x+2 &amp; 3x+2 &amp; 4x+2 &amp; 5x+2 &amp; 6x+2 \newline
3 &amp; x+3 &amp; 2x+3 &amp; 3x+3 &amp; 4x+3 &amp; 5x+3 &amp; 6x+3 \newline
4 &amp; x+4 &amp; 2x+4 &amp; 3x+4 &amp; 4x+4 &amp; 5x+4 &amp; 6x+4 \newline
5 &amp; x+5 &amp; 2x+5 &amp; 3x+5 &amp; 4x+5 &amp; 5x+5 &amp; 6x+5 \newline
6 &amp; x+6 &amp; 2x+6 &amp; 3x+6 &amp; 4x+6 &amp; 5x+6 &amp; 6x+6
\end{matrix}
$$

## 1.2 Calculating with polynomials

### 1.2.1 Multiplying Polynomials

The multiplication is written as: polynomial 1 ⊗ polynomial 2. To perform this multiplication, we do the same as we would do with for example: (2x + 2) * (4x + 3). But this time, we do modulo our prime on the end!

__Example:__ 123x4+76x2+7x+4 ⊗ 196x4+12x3+225x2+4x+76 %251 for prime = 251

![multiplying_polynomials](https://drive.google.com/uc?export=view&amp;id=0B-cbbSwiSpTPbkdTWHF2M0luT0U)

Here we can see that the result:
$$12x^2+221x^7+152x^6+15x^5+208x^4+170x^3+178x^2+46x+53$$

### 1.2.2 Dividing Polynomials

Dividing polynomials is also easy, but we have to pay attention. If the coefficient of the divisor it's head grade = 1 then we can do a normal division like we saw when we were 12 years old (we just use some bigger numbers now).

#### 1.2.2.1 Head grade divisor is 1

__Example:__ 12x8+221x7+152x6+25x5+208x4+117x3+150x2+30x+53 / x5+x4+12x3+9x2+7

![dividing_polynomials](https://drive.google.com/uc?export=view&amp;id=0B-cbbSwiSpTPT0Q5Z1VCT3dLOTQ)

This results into:
$$12x^3+209x^2+50x+120 \otimes x^5+x^4+12x^3+9x^2+7 \oplus 117x^4+151x^3+117x^2+182x+217 \text{ mod 251}$$

which is just the result multiplied by the divisor and the remainder added to it.

#### 1.2.2.2 Head grade divisor &gt; 1

If the head grade &gt; 1, then we have to multiply both the divisor and the polynomal by (head grade) ^ -1 mod p

So this means if we got this division:
$$12x^8+221x^7+152x^6+25x^5+208x^4+117x^3+150x^2+30x+53 / 3x^5+x^4+12x^3+9x^2+7$$

becomes

$$4x^8+241x^7+218x^6+92x^5+153x^4+39x^3+50x^2+10x+185 / x^5+84x^4+4x^3+3x^2+86$$

On the end we just have to remultiply the remainder by the head coeficient of the divisor, and then we got our result

Steps executed:
![dividing_polynomials_2](https://drive.google.com/uc?export=view&amp;id=0B-cbbSwiSpTPa2k3UThHR19VcUE)

### 1.2.3 The Euclidean Algorithm For Polynomials

The euclidean algorithm was already explained in the first post for discrete math [http://desple.com/post/104343618742/discrete-math-fields-prime-fields-part-1](http://desple.com/post/104343618742/discrete-math-fields-prime-fields-part-1) and we are now able to do this with polynomials too.

## 1.3 Group Tables

We got 2 different group tables, the additive group table and the multiplicative. We will first start by constructing the additive group table since this is the easiest one. To construct this we follow these steps:

1. Find the elements belonging to the GF being given (Write only the coefficients, easier to calculate with)
2. When we found the elements, create a table with the X and Y values being the elements from the GF
3. Now we calculate the sum of the X and Y values and fill in our table

&gt; **Note:** When filling in the table, don't forget that we are working **mod p**

**Example:** We will create the additive table for GF(27)

**Basics of the GF:**
GF(27), p = 3, n = 3, q = 27

**1) Elements**

Complete List:

$$
\begin{matrix}
0 &amp; 1 &amp; 2 &amp; x &amp; x+1 &amp; x+2 &amp; 2x &amp; 2x+1 &amp; 2x+2 \newline
x^2 &amp; x^2+1 &amp; x^2+2 &amp; x^2+x &amp; x^2+x+1 &amp; x^2+x+2 &amp; x^2+2x &amp; x^2+2x+1 &amp; x^2+2x+2 \newline
2x^2 &amp; 2x^2+1 &amp; 2x^2+2 &amp; 2x^2+x &amp; 2x^2+x+1 &amp; 2x^2+x+2 &amp; 2x^2+2x &amp; 2x^2+2x+1 &amp; 2x^2+2x+2
\end{matrix}
$$

Just the coefficients:

$$
\begin{matrix}
0 &amp; 1 &amp; 2 &amp; 10 &amp; 11 &amp; 12 &amp; 20 &amp; 21 &amp; 22 \newline
100 &amp; 101 &amp; 102 &amp; 110 &amp; 111 &amp; 112 &amp; 120 &amp; 121 &amp; 122 \newline
200 &amp; 201 &amp; 202 &amp; 210 &amp; 211 &amp; 212 &amp; 220 &amp; 221 &amp; 222
\end{matrix}
$$

**2) &amp; 3) Create table with X and Y as the elements, and calculate MOD P**

![galois_field_27](https://drive.google.com/uc?export=view&amp;id=0B-cbbSwiSpTPOEEwZDN4YVN4aW8)

If we now want to calculate the multiplicative field, then we just need to add a 0 column and a 0 row in the beginning and then we have our multiplicative result:

![galois_field27_multiplicative](https://drive.google.com/uc?export=view&amp;id=0B-cbbSwiSpTPZmdzNVB3dU1lV0E)

## 1.4 irreducible Polynomials

### 1.4.1 Number of irreducible Polynomials

We know that there are pn amount of monic polynomials. By using the Mobius Inversion, we can calculate how many there are irreducible.

$$
\frac{1}{n} \sum_{d|n} \mu() * p^{\frac{n}{d}}
$$

**Example:** How many polynomials are irreducible for (F66, ⊕, ⊗)

$$
\frac{6^6 - 6^3 - 6^2 + 6}{6} = 7735
$$

Which means that there are 7735 of the 46656 polynomials that are irreducible for the prime 6 with grade 6

### 1.4.2 Checking if a Polynomial is irreducible

To check if a Polynomial is irreducible, we have to check if it has not common factors mod p with the polynomials of xpi - x, for every i &lt;=n / 2

Some examples for checking:

* **Fp2**: check xp - x
* **Fp3**: check xp - x
* **Fp4**: check xp - x and xp2
* **Fp5**: check xp - x and xp2
* **Fp6**: check xp - x , xp2 and xp3
* **Fp7**: check xp - x , xp2 and xp3

&gt; **Note:** We wrote - everywhere, this is correct since we still have to do **mod p** afterwards. So this could become + if we would do this for for p = 2 (since -1 mod 2 = +1)!

**Example:** Find an irreducible polynomial with n = 7 for F128

128 ==&gt; p = 2, n = 7

Since n = 7, we know that we have to check for x2 + 1, x4 + 1 and x8 + 1

Now we pick a polynomial that could be irreducibel and is monic. For example: x7 + x2 + 1

To check if this is irreducibel, we need to be sure this polynomial can not be divided by the 3 checks that we have placed. We check this by using the Euclidean algorithm and the dividing of Polynomials.

![check_irreducible](https://drive.google.com/uc?export=view&amp;id=0B-cbbSwiSpTPV1lkTlJXRDR5bGM)

&gt; A lot of irreducible polynomials have been found, we can find those in the FIPS 186 standard ([FIPS186-1](http://csrc.nist.gov/publications/fips/fips1861.pdf), [FIPS186-2](http://csrc.nist.gov/publications/fips/archive/fips186-2/fips186-2.pdf), [FIPS186-3](http://csrc.nist.gov/publications/fips/fips186-3/fips_186-3.pdf), [FIPS186-4](http://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.186-4.pdf))

## 1.5 Primitive Elements

If we found an Irreducible Polynomial, then we have to find a primitive element ω of the multiplicative group. We can do this by using the method that I explained in my first blog post about Discrete math [http://desple.com/post/104343618742/discrete-math-fields-prime-fields-part-1](http://desple.com/post/104343618742/discrete-math-fields-prime-fields-part-1)

I also refer to this post for finding the discrete logarithm for an index of a primitive root using the baby-step giant-step method.

## 1.6 Inverse Elements

We can calculate the inverse of an element using the Euclidean Algorithm.

**Example:** (x4+x3+x2)-1

![inverse_elements](https://drive.google.com/uc?export=view&amp;id=0B-cbbSwiSpTPSXhwa25wbGdWX3M)

Following the solution above, we can see that the inverse is equal to: x6 + x3 + x2

## 1.7 Calculating with indices

### 1.7.1 Method

To perform caslculations in Finite fields we have to choose between 2 methods

* We identify the coordinates in a n-dimensional grid for the polynomial with grade &lt; n
* **Advantage:** Additive Calculation are just additions mod p
* **Disadvantage:** Multiplicative Calculations require inverse elements and are therefor harder
* We identify the elements by comparing it's index to a primitive element ω (ω is randomly chosen)
* **Advantage:** We simplify multiplicative calculations to 1 additive calculations modulo(q - 1)
* **Disadvantage:** Additive Calculations are harder, but we can still perform them if we have a list of all it's elements en their indices and we have an additive group table where the elements are identified by it's indices)

### 1.7.2 Constructing the needed additive group table

1. Calculate 1 row by using the list of all the elements and their indices. (Easiest on row index = 0)
2. Calculate the following rows by doing the previous cel +1 mod (q-1) and shift 1 position

**Example:** Calculate the group table for F4, μ=x2+x+1 and ω=x

**1)** Calculate the elements in this group (see 1.1)
F4 = 22, so 4 elements. These elements are:

$$
\begin{matrix}
0 &amp; 1 \newline
1 &amp; x + 1
\end{matrix}
$$

**2)** Assign indices to every element and put them as the x and y value for the table (or more dimensions if n &gt; 2) (**Note:** if element is 0, then indice is ∞! (This is because an element with itsself will return 0 after modulo))

I wrote the x and y indices in bold.

||⊕|**0**|**1**|**2**|**∞**|
| :-: | :-: | :---: | :---: | :---: | :---: |
|1|**0**|
|x|**1**|
|x+1|**2**|
|0|**∞**|

**3)** Once we found the indices, we can just do the addition for the elements

For the first row this becomes:

* indice 0 and 0 = ∞, same indices is ∞)
* indice 1 and indice 0 = 1 + x = x + 1 = indice 2
* indice 2 and indice 0 = x + 1 + 1 = x + 2 = x (since modulo 2) = indice 1
* indice ∞ and indice 0 = 0 + 1 = 1 = indice 0

||⊕|**0**|**1**|**2**|**∞**|
| :-: | :-: | :---: | :---: | :---: | :---: |
|1|**0**|∞|2|1|0
|x|**1**|2|∞|0|1
|x+1|**2**|1|0|∞|2
|0|**∞**|0|1|2|∞

### 1.7.3 Constructing the needed multiplicative table

We do the same steps as the method for constructing the additive group, only this time we will do a multiplicative operation instead of an additive

**Example:** Multiplicative table for F&gt;sub&gt;4, μ=x2+x+1 and ω=x

**1)** Calculate the elements in this group (see 1.1)
F4 = 22, so 4 elements. These elements are:

$$
\begin{matrix}
0 &amp; 1 \newline
1 &amp; x + 1
\end{matrix}
$$

**2)** Once we found the indices (See step 2 for the additive group table in 1.7.2), we can just do the multiplication for the elements

For the first row this becomes:

||⊕|**0**|**1**|**2**|**∞**|
| :-: | :-: | :---: | :---: | :---: | :---: |
|1|**0**|0|1|2|∞
|x|**1**|1|0|0|∞
|x+1|**2**|2|0|0|∞
|0|**∞**|∞|∞|∞|∞

&gt; We can clearly see that we got more 0's in this table. This is because when we multiply the indices together, and we get a value that is not in our table. Then we write ∞

## Concluding

There is only a field with order q if q is the power of a prime number!

But how can we find finite cyclical groups where we can write the number of elements as pn - 1?

This solution will be provided in part 3

Fields - Galois 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 P1⊞P2.
* ∞ 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 P1⊞P2 for the elliptical curbes (E/Fpn) over the finite fields (Fpn). Which allows us to reduce the amount of Weirstrass equations to 5 cases:

**Supersingular Cases**

* (E/F2n, ⊞), E: y2 + cy = x3 + ax + b
* (E/F3n, ⊞), E: y2 = x3 + ax + b

**Not-Supersingular Cases**

* (E/F2n, ⊞), E: y2 + xy = x3 + ax2 + b
* (E/F3n, ⊞), E: y2 = x3 + ax2 + b

**Over fields with characteristic p ≥ 5**

* (E/Fpn, ⊞), E: y2 = x3 + ax + b

## 1.2 Number of points

The number of points (#E) on a elliptical curbe (E/Fq=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/Fp, ⊞), if we know this we can get the number of points for #(E/Fpn, ⊞), 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/Fp, ⊞) and ε0 = 2
* εn = ε1εn - 1 - pεn - 2

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

What do we know:

* We know that by applying Fq = pn that F65536 = 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

&gt; 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/F37, ⊞) |ε| ≤ 12 ==&gt; 26 ≤ #E ≤ 50)

## 1.3 Curves over Characteristic (F) ≥ 5

Let's say we got a Weirstrass Equation that is of the form: **E: y2 = x3 + ax + b**, we know that this is a (E/F3n, ⊞) 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: y2 = x3 ⊕ a⊗x ⊕ b** (Note: the power is also multiplicative!).

### 1.3.1 Formulas

2P = ∞

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

We can now calculate (x3, y3) = (x1, y1) ⊞ (x1, y1)

1. z = (y2 ⊖ y1) ⊘ (x2 ⊖ x1)
2. x3 = z2 ⊖ x1 ⊖ x2
3. y3 = z ⊗ (x1 ⊖ x3) ⊖ y1

### 1.3.2 Example
**Question: We have (E/F5), a=4, b=1, n=1 (so we have modulo 5) and E: y2 = x3 + ax + b**

We know that E: y2 = x3 + ax + b = E: y2 = x3 + 4x + 1

We can calculate x3 + 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 x3 + 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
| **x3 + 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' --&gt; 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/F2n

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” = z2 ⊕ z ⊕ a
4. y” = x2 ⊕ (z ⊗ x'') ⊕ x''

We can now calculate (x3, y3) = (x1, y1) ⊞ (x1, y1)

1. z = (y1 ⊕ y2) ⊘ (x1 ⊕ x2)
2. x3 = z2 ⊕ z ⊕ x1 ⊕ x2 ⊕ a
3. y3 = z ⊗ (x1 ⊕ x3) ⊕ x3 ⊕ y1

### 1.4.2 Example

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

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

Note: We are using the additive table here for the field F23

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

| | | | | | | | | |
|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|
| **x** | 0 | 1 | 2 | 3 | 4 | 5 | 6 | ∞
| **x3** | 0 | 3 | 6 | 2 | 5 | 1 | 4 | ∞
| **0 ⊗ x2** | 0 | 2 | 4 | 6 | 1 | 3 | 5 | ∞
| **x3 ⊕ 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' --&gt; 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/Fq=pn, ⊞) is cyclical
* μ(#E)=0, then we need to check this, check the methods 1.3 and 1.4 for this.