Finite fields Flashcards
Field
A field F is a nonempty set, S, with two binary operations, + and ·, and two different elements of S, 0 and 1, such that the following axioms are satisfied.
1. ∀x, y: x + y = y + x
2. ∀x, y, z: (x + y) + z = x + (y + z)
3. ∀x: x + 0 = x
4. ∀x ∃(−x): x + (−x) = 0
5. ∀x, y: x · y = y · x
6. ∀x, y, z: x · (y · z) = (x · y) · z
7. ∀x: x · 1 = x
8. ∀x ≠ 0 ∃x^{−1}: x · x^{−1} = 1
9. ∀x, y, z: x · (y + z) = x · y + x · z
Classical examples of fields are the rational numbers Q, the real numbers R, and the complex numbers C.
Finite field
If the number of elements, |S|, in S is finite we have a finite field and it is an interesting fact that these can be completely determined in the sense that these exist if and only if the number of elements is a power of a prime and they are essentially unique:
Let p be a prime and let S = {0, 1, … , p − 1}. Let + and · denote addition and multiplication modulo p respectively. Then (S, +, ·, 0, 1) is a finite field with p elements which we denote F_p.
Ternary field
F_3, that has elements 0, 1, 2. You use mod 3 in this field.
Order
Let F be a finite field with q elements, and let a ∈ F{0}. The order of a, ord (a), is the smallest positive integer s such that a^s = 1.
Additionally, F has an element of order q − 1.
Let F be a finite field with q elements, then F has an element of order q − 1.
Primitive element
F contains an element α, a so-called primitive element, such that F{0} = {α^i |i = 0, 1, … , q − 2} and α^{q−1} = 1 . Therefore α^i · α^j = α^{(i+ j) mod (q−1)}.
ord(α) = q-1
The order of any nonzero element in a finite field with q elements divides q − 1.
Irreducible polynomium
A polynomial f (x) ∈ F[x] is called irreducible if f (x) = a(x)b(x) implies that deg(a(x)) = 0 or deg(b(x)) = 0 (e.g. either a(x) or b(x) is a constant).
Set of polynomials in F
F[x] denotes the set of polynomials with coefficients from F, i.e. expressions of the form
a_n * x^n + … + a_1 * x + a_0
where a_i ∈ F. We have the notion of the degree of a polynomial (denoted deg) and can do addition and multiplication of polynomials.
A polynomial of degree n has at most n zeroes.
The field F_{2^m}
As elements of F_{2^m} we take the 2^m m-tuples with elements from F_2 and addition is defined coordinatewise. This implies that a + a = 0. It is easy to see that the first four axioms for a field are satisfied.
Multiplication is somewhat more complicated. Let f (x) ∈ F_2[x] be an irreducible polynomial of degree m. Let a = (a_0, a_1, … , a_{m−1}) and b = (b_0, b_1, … , b_{m−1}) and therefore a(x) = a_{m−}1 * x^{m−1} + … +a_1 * x + a_0 and b(x) = b_{m−1} * x_{m−1} + … +b_1 * x+b_ 0. We define the multiplication as a(x) * b(x) modulo f (x), i.e. if a(x) * b(x) = q(x) * f(x) + r(x), where deg(r (x)) < m, we set r = (r_0, r_1, … , r_{m−1} ). If we let 1 = (1, 0, … , 0) we see that 1 · a = a.
With the addition and multiplication we have just defined we have constructed a field. This is fairly easy to see, again the most difficult part is to prove the existence of a multiplicative inverse for the nonzero elements.
To this end we copy the idea from F_p . Let a ∈ F_{2^m} {0}. The set A = { a · h|h ∈ F_{2^m} {0} } does not contain 0 since this would, for the corresponding polynomials, imply that f (x)|a(x) or f (x)|h(x). Moreover the elements of A are different since if a · h_1 = a · h_2 we get for the corresponding polynomials that f (x)|a(x)(h_1(x) − h_2(x)), and since f (x) is irreducible this implies f (x)|a(x) or f (x)|h1(x)−h2(x). But this is only possible if h_1(x) = h_2(x), since f (x) has degree m but both a(x) and h_1(x) − h_2(x) have degree < m. This gives that A = F_{2^m} {0} and in particular that 1 ∈ A.
It can be proven that for any positive integer m there exists an irreducible polynomial of degree m with coefficients in F_2 and therefore the above construction gives for any positive integer m a finite field with q = 2^m elements; we denote this F_q . It can also be proven that essentially F_q is unique.
