Finite Field
In this section we will talk about something in abstract algebra, and i’m trying to make it painless and simple.
Finite Fields is a vary important topic in cryptography and it is used
in many encryption algorithms such as AES encryption algorithm.
I will skip a lot of branches in abstract algebra such as (modular, arithmetic Euclidean algorithms … etc) and you can find it easily on Wikipedia.
Starting with some terminology
 A set : Is a group of elements or members represented as a unit, set can be described in several ways such as braces {5,13,27,30}.
 A field : Is a set of elements with two binary operations addition and multiplication.
Fields have the following properties:
 Closure under addition which if a and b belong to S, then a+b is also in S.
 Associativity of addition which a+(b+c) = (a+b)+c and a,b,c in S.
 Additive identity which there is an element 0 in R such that a+0 = 0+a = a for all in S.
 Additive inverse which for each a in S there is an element a in S such that a+(a)=(a)+a =0.
 Commutativity of addition which a+b=b+a for all a.b in S.
 Closure under multiplication which if a and b belong to S , then ab is also in S.
 Associativity of multiplication which a(bc) = (ab)c for all a,b,c in S.
 Distributed laws which a(b+c) = ab+ac for all a,b,c in S.
 Multiplication Identity which there is an element 1 in S such that a1 = 1a = a for all in S.
 No zero division which if a,b in S and ab=0, then either a=0 or b=0.
 Multiplication inverse which if a belongs to S and a != 0 ,there is an element \({a}^{1}\) is S such that \({aa}^{1}\) =1.
Finite Fields have a property called “order”, order in finite field is the number of the elements in the filed and this order must be a power
of a prime number GF(\({P}^{n}\)) GF is stands for Galois Field , and
Galois is a mathematician who create the finite field, P is a prime number, n : is a positive integer.
In finite field we preform operations such as addition and multiplication without leaving the set
For example:
in GF(7), so the set will be {0,1,2,3,4,5,6} six elements start from 0 to p1, if we preform addition operation 5+4=9 mod(7) = 2 and 2 is in the set.
AES encryption algorithm work under GF(\({2}^{8}\)) but in a binary representation, we will represent Galois Field by using polynomial, and it’s much easier.
In GF(\({2}^{8}\)), if we want to represent GF(91) first we need to convert it into a binary 01011011, second convert it into a polynomial under one variable x \(({x}^{7})+({x}^{6})+({x}^{5})+({x}^{4})+({x}^{3})+({x}^{2})+({x}^{1})+1\) and all zeros are discarded from the polynomial, so the polynomial representation will be \(({x}^{6})+({x}^{4})+({x}^{3})+x+1\)

Addition operation in polynomial representation in GF(\({2}^{8}\)): To preform addition operation simply we will add two polynomials and then we take mod(2) to reduce 2 coefficients (remove any 2 coefficients).
For example:
In GF(\({2}^{8}\)) add 83 and 249
83 = 01010011 = \(({x}^{6})+({x}^{4})+x+1\)
249 = 11111001 = \(({x}^{7})+({x}^{6})+({x}^{5})+({x}^{4})+({x}^{3})+1\)
add 1 and 2 = \((({x}^{7})+2({x}^{6})+({x}^{5})+2({x}^{4})+({x}^{3})+x+2)mod(2)\)
remove 2 coefficients \(2({x}^{6})+2({x}^{4})+2\)
= \(({x}^{7})+({x}^{5})+({x}^{3})+x\) (polynomial representation)
= 10101010 (binary representation)
= 170 (decimal representation) 
Addition operation in binary representation in GF(\({2}^{8}\)): To add two numbers in binary representation in GF(\({2}^{8}\)) form we just preform XOR operation instead of arithmetic addition.
For example :
In GF(\({2}^{8}\)) add 83 and 249
83 = 01010011
249 = 11111001
01010011 ⊕ 11111001 = 10101010 = 170 
Multiplication in polynomial representation in GF(\({2}^{8}\)): Here we will multiply two polynomials and then we take mod(2) to reduce 2 coefficients, but if the results exceed 255 in binary or 11111111 in binary or \({x}^{7}\) in polynomial then we use irreducible polynomial to reduce the results by a long division the result over the irreducible polynomial and the result is the reminder of division, and in GF(\({2}^{8}\)) irreducible polynomial \(m(x) = ({x}^{8})+({x}^{4})+({x}^{3})+x+1\)
For example :
In GF(\({2}^{8}\)) multiply 83 and 249
83 = \(({x}^{6})+({x}^{4})+x+1\)
249 = \(({x}^{7})+({x}^{6})+({x}^{5})+({x}^{4})+({x}^{3})+x+1\)
multiply 1 and 2 and take mod(2)
= \(({x}^{13})+({x}^{12})+({x}^{7})+({x}^{6})+({x}^{4})+({x}^{3})+x+1\)
OR by using MATLAB and get the same result
a = gf( [1 0 1 0 0 1 1] );
b = gf( [1 1 1 1 1 0 0 1] );
c = conv(a,b)
The results here exceed \({x}^{7}\) then we preform a long division by the irreducible polynomial and the result is the reminder
\(({x}^{13})+({x}^{12})+({x}^{7})+({x}^{6})+({x}^{4})+({x}^{3})+x+1\)
—————————————————————————*
\(({x}^{8})+({x}^{4})+({x}^{3})+x+1\)
Result = \(({x}^{5})+({x}^{4})+x\)
Remainder = \(({x}^{5})+({x}^{4})+({x}^{3})+({x}^{2})+1\)
The result
= \(({x}^{5})+({x}^{4})+({x}^{3})+({x}^{3})+1\) (polynomial representation)
= 00111101 (binary form)
= 61 (decimal form)
OR by using MATLAB and get the same result
a = gf( [1 1 0 0 0 0 1 1 0 1 1 0 1 1] );
b = gf( [1 0 0 0 1 1 0 1 1] );
[q,r] = deconv(a,b)
Note 1: If you found this hard to understand you can use GFCalculator to preform addition and multiplication on two decimal numbers in GF(\({2}^{8}\))
Note 2: You can multiply two polynomials by using Euclidean algorithm (Extended Euclid).
Note 3: A polynomial is irreducible if it cannot be expressed as the product of two or more such polynomials.
Note 4: \(m(x) = ({x}^{8})+({x}^{4})+({x}^{3})+x +1\) is one of 30 possible irreducible polynomials of degree 8.