5 Finite fields Flashcards
Why use finite fields in coding?
Already thought of as vector space in Sⁿ, further think of strings
x=x₁x₂…xₙ =(x₁,x₂,…xₙ)
as vectors, so that we can add them, and multiply by scalars.
we want to define + and * and division but S is finite- we want it to be a finite field
def 5.1 commutative ring
A commutative ring is a set F equipped with 2 associative and commutative operations
+ : F × F → F, × : F × F → F
(we will write ab for ×(a, b) = a × b), such that:
(1) × is distributive over +:
a(b + c) = (ab) + (ac)
(2) there is an additive identity element 0 ∈ F, so that
a + 0 = 0 + a = a ∀a
(3) there is a multiplicative identity element 1 ∈ F, so that
a1 = 1a = a ∀a
(4) Every a ∈ F has an additive inverse −a such that
a + (−a) = 0
The integers form a commutative ring.
For m an integer ≥ 1 and a a ring element we put
ma
For m an integer ≥ 1 and a a ring element we put
ma= a+…+a
(m copies)
def 5.3 A field
A field is a commutative ring F ̸= {0} such that
(5) Every a ∈ F \ {0} has a multiplicative inverse a⁻¹
such that a(a⁻¹) = 1.
The characteristic of F is the smallest m ≥ 1 such that m1F = 0F
if it exists and 0 otherwise. The characteristic of F is zero or a
prime; if it is zero, then F is infinite.
examples of fields
The obvious example is the real numbers. The rational numbers also work. As do the complex numbers.
The integers do not work, since 2 has no integer multiplicative
inverse.
The challenge is to find finite sets F that can have all these properties. A great source of such examples comes from thinking about modular arithmetic:
Define a relation of congruence modulo 5 on Z
equivalence classes
Define a relation of congruence modulo 5 on Z by a ≡ b if
a − b = 5m for some integer m.
[0] = {……, −10, −5, 0, 5, 10, ……} ,
[1] = {……, −10 + 1, −5 + 1, 0 + 1, 5 + 1, 10 + 1, ……} ,
and indeed for r ∈ Z:
[r] = {……, −10 + r, −5 + r, 0 + r, 5 + r, 10 + r, ……} .
Any equivalence class [r] is equal to [0], [1], [2], [3] or [4], and these
5 are distinct
forming Z_p
when we do ordinary integer arithmetic we find that
it respects these classes. That is, if a′, b′ are congruent to a, b
respectively, then
a′ + b′ is congruent to a + b and
a′b′ is congruent to ab.
So we may define
[a] + [b] = [a + b] and [a][b] = [ab] .
Example:
1 + 2 = 3 21 + (−98) = −77
Z_p
The resulting ring is denoted
Z_p = Z/pZ, where at this stage p is
any natural number. Thus Zp is a set with + and × which are
commutative and associative, distributive…
p=5
Z_5
inverses?
Example: For p = 5 the additive inverses of [0], [1], … are given by
[0] + [0] = [0]
[1] + [4] = [0]
[2] + [3] = [0]
so that [0]=-[0]; [4]=-[1] and [3]=-[2].
What about multiplicative inverses? Is there an [x] such that
[2][x] = [1]?
If we are working in Z5 then: Yes!
[2][3] = [6] = [1]. And
[4][4] = [16] = [1].
THM 5.7 Z_p is a field?
Z₅ is a field.
On the other hand Z4 is a commutative ring, but not a field. The
complete row of the multiplication table for [2] is
[2][0] = [0]
[2][1] = [2]
[2][2] = [0]
[2][3] = [6] = [2]
Since none of the right hand sides is [1] we see that [2] does not
have a multiplicative inverse.
Thm 5.8 when is Zₚ a field?
(i) Z_p is a field iff p is prime.
(ii) If F is a finite field of order (=size) q and characteristic p,
then q = pᵉ for some integer e ≥ 1.
(iii) If q = pᵉ
for some prime p and integer e ≥ 1, then there exist a finite field F_q of order q and it is unique up to isomorphism.
Thm 5.8 when is Zₚ a field? explanation
Part (i) can be proved as an exercise and part (ii) is easy as we will
see later.
Part (iii) is standard in algebra textbooks, but for now we will
content ourselves with understanding the statement.
So, what about part (iii)?
we can construct fields of prime order. But fields Z_(p^2) are not prime, fields of order p^2 aren’t these then… what are they?
constructing fields not Z_p:
adjoining i to R: the smallest field (as must be closed) containing R and i is C
adjoining i to Q: construct a complex rational field bigger than Q but smaller than C
what we have done is added to Q a new number b which obeys v²+1=0
general elemement
a+bv a, b ∈ Q.
closed under addition and multiplication
(a ₁+b ₁v) +(a₂+b₂v)= (a₁+a₂) +(b ₁+b₂)v
(a ₁+b ₁v)*(a₂+b₂v)=
((a₁a₂) - (b₁b₂)) + (a₁b₂+ b₁a₂)v
multiplicative inverse of v is -v
since v(−v) = −v^2 = 1
Extending Z₂
F₄
prime p=2 Z₂ extending this field
By adding an element that obeys a polynomial equation with coefficients in Z₂ and irreducible.
The only one is
f (x) = 1 + x + x²
Adjoining root α of f to Z₂ we get:
{0, 1, α, 1 + α}
The inverse of α is 1 + α, since
α(1 + α) = α + α² = −1 = 1 (mod p)
This field is called F₄
(new element as root wasnt prev in)
lemma 5.11 field F properties for finite fields
Let F be a field of prime characteristic p.
(i) For a, b ∈ F we have
(a + b)ᵖ = aᵖ +bᵖ
(ii) If F is finite then φₚ : α → αᵖ
is an automorphism of F,
i.e.
it is bijective, preserves addition and multiplication, and maps 0 to 0 and 1 to 1.
proof: notes
