7 Algebraic Structures and Finite Fields 1

Dr Kulothungan

Learning Objectives

Ø  To review the concept of algebraic structures

Ø   To define and give some examples of groups, rings, fields

Ø   To review the concept of Ring and Field

Ø   To define the purpose of Finite Field in  cryptography

Ø   To discuss about the Galois field to perform modulo prime p

Ø   To understand Galois fields with some examples.

8.1 Algebraic Structures:

Abstract algebra is the study of algebraic structures. Such a structure consists of a set together with one or more binary operations, which are required to satisfy certain axioms. For example, here is the definition of a simple algebraic structure known as a group.

8.2 Group

A group is a set G together with a binary operation ∗ on G, satisfying the following axioms:

1.    The  operation  ∗ is  associative.  That is,

a  ∗ (b ∗ c) = (a ∗ b) ∗ c for all a, b, c ∈ G.

2.    There exists an element e ∈ G with the property that

a ∗ e = e ∗ a = a

   for all a ∈ G. (This element e is called the identity element of G.)

3.    For each element a ∈ G, there exists an element a−1 ∈ G such that

a   ∗ .a⁻¹. = .a⁻¹. ∗ a

=    e.

(The element a⁻¹  is called the inverse of a.)

The binary operation ∗ in this definition may be any operation at all, such as addition, multiplication, or composition of functions. Any set of elements with an operation that satisfies these axioms forms a group. For example:

•  The set Z of integers forms a group under the operation of addition. In particular, addition is associative, the element 0 is an additive identity, and every integer has an additive inverse.

•  The set R − {0} of nonzero real numbers forms a group under the operation of multiplication. Note that zero must be excluded, since it does not have a multiplicative inverse.

•  The set GL(n, R) of all invertible n × n matrices forms a group under the operation of matrix multiplication. In this case, the identity element is the

n × n identity matrix.

Groups are a particularly simple algebraic structure, having only one operation and three axioms. Most algebraic structures have more than one operation, and are required to satisfy a long list of axioms.

Here is a partial list of the most important algebraic     structures:

•  A group is an algebraic structure with a single operation, as defined above. Groups are closely associated with the idea of symmetry, and most groups that arise in mathematics are groups of symmetry transformations, with the operation being composition of functions.

•  A field is an algebraic structure with addition and multiplication, which obey all of the usual rules of elementary algebra. Examples of fields include the rational numbers Q, the real numbers R, and the complex numbers C.

•  A ring is a more general algebraic structure with addition and multiplication. Unlike a field, a ring is not required to have multiplicative inverses, and the multiplication is not required to be commutative. A good example of a ring is the set of all n× n matrices under the operations of matrix addition and matrix multiplication. The integers Z also form a ring under the operations of addition and multiplication.

•  A module is similar to a vector space, except that the scalars are only required to be elements of a ring. For example, the set Zn of n-dimensional vectors with integer entries forms a module, where “scalar multiplication” refers to multiplication by integer scalars.

Because algebraic structures are inherently abstract, the names for them are fairly arbitrary. Words like “group”, “module”, and “field” are just interchangeable collective nouns, and you should not ascribe any importance to which structure has which name. The word “ring” is also in this category—it is meant to refer to an association or coalition, such as a smuggling ring or a ring of spies, and should not convey any sense of circularity.

The structures listed above are only a sample of the many algebraic structures of importance in mathematics. Many fields of mathematics involve their own special algebraic structures, and new algebraic structures are defined all the time. To give you a sense of scale, the online encyclopedia Wikipedia currently has articles on over a hundred different algebraic structures, and this represents only a small fraction of those that have been investigated in the mathematical literature.

8.3 Fields

The most familiar form of algebra is the elementary algebra that you learned in high school, namely the algebra of the real numbers. From an abstract point of view, this is the algebra of fields.

A field is a set F together with two binary operations + (the addition operation) and (the multiplication operation), that satisfy the following axioms:

The addition operation is associative.  That is,

a + (b + c) = (a + b) + c

for all a, b,c  ∈ F .

The addition operation is commutative.  That is,

a + b = b + a ,for all a,b ∈ F There exists a special element of F called the additive identity, denoted by the symbol 0. This element has the property that a + 0 = a , for all a ∈ F

i.           For each element a ∈ F , there is an element −a ∈ F , called the additive inverse of a, with the property that

a   + (−a) =  0.

ii. The multiplication operation is associative. That is,

a · (b · c) = (a · b) · c

for all a, b, c ∈ F .

iii.            The multiplication operation is commutative. That is,

a · b = b · a

for all a, b ∈ F .

iv.           There exists a special element of F called the multiplicative identity, denoted by the symbol 1.This element has the property that

a · 1 = a

for all a ∈ F .

v.           For each element a ∈ F other than 0, there exists an element a−1  ∈ F , called  the multiplicative  inverse of a, with the property       that

a    · a−1 = 1.

vi.           The multiplication operation distributes over the addition operation. That is,

a   · (b + c) = (a · b) +(ac)

for all a, b, c ∈ F .

Note that the axioms for a field are precisely the axioms for algebra on the real numbers. As a result, the real numbers R form a field under the usual operations of addition and multiplication. However, the real numbers are not the only possible field. Indeed, you are already familiar with a few other examples:

•  The rational numbers Q form a field under the usual operations of addition and multiplication. In particular, we can add or multiply two elements of Q to obtain another element of Q, and these operations obey all of the axioms listed above.

•  The complex numbers C form a field under the commonly defined operations of addition and multiplication. Complex numbers do obey all of the listed axioms for a field, which is why elementary algebra works as usual for complex numbers.

The following example discusses another class of fields that we shall be using repeatedly.

EXAMPLE 1 Integers Modulo n

If n ≥ 2, let Zn denote the set {0, 1, . . . , n − 1} under the operations of addition

and multiplication modulo n . For example, here are the addition and multiplication tables for Z₅:

It is not hard to see that Zn satisfies most of the axioms for a field, but it is not clear that every nonzero element of Z n has a multiplicative inverse (as is required by axiom 8). For Z5, we can see from the multiplication table that every element has an inverse. In particular,

1⁻¹ = 1, 2⁻¹ = 3, 3⁻¹ = 2, and 4⁻¹ = 4, Thus Z₅ is a field.

The same is not true for Z6. Here is the multiplication table modulo  6:

As you can see from this table, 1⁻¹ = 1 and 5⁻¹ = 5 in Z6, but the elements 2, 3, and 4 do not have multiplicative inverses.

The following theorem from number theory characterizes which elements have multiplicative inverses. We will not prove this theorem here:

Let n ∈ N, and let k ∈ Zn. Then k has a multiplicative inverse in Zn if and only if k and n are relatively prime.

Theorem 1        Multiplicative Inverses in Zn

Here relatively prime means that k and n have no common prime factors, their greatest common divisor is 1. This explains why 2, 3, and 4 have no multiplicative inverses in Z6 — all of these numbers have a factor in common with 6. We can immediately conclude the following:

Zn  is a field if and only if  n is  prime.

Corollary 2   Prime Fields:

This gives us a large class of fields that are very different from the real numbers. However, you should be aware that we have hardly exhausted the list of fields. For example, here are the addition and multiplication tables for a field with four elements:

Note that this is not the same as Z4, since among other things Z4 is not a field. The lesson is that not every finite field comes from modular arithmetic.

There are similar fields with eight and nine elements, although surprisingly it is not possible to define a field with six or ten elements. Indeed, a famous theorem of field theory asserts that there exists a field with n elements if and only if n is a power of a prime.

8.4 Algebra of Fields

By definition, the elements of a field satisfy exactly the same algebraic axioms as the real numbers. As a result, everything you know about algebra for real numbers translates directly to algebra for the elements of any field. This includes virtually everything you know about elementary algebra, as well as basic linear algebra.

Of course, the definition of a field involves only addition and multiplication, but we usually think of algebra as involving the four operations of addition, subtraction, multiplication, and division. Fortunately, it is not difficult to define subtraction and division for elements of a field.

Definition: Subtraction and Division in Fields Let F be a field, and let a, b ∈ F .

(a) The difference of a and b is defined by the  formula

a   − b = a + (−b),

where −b is the additive inverse of     b.

(b)     If b ƒ= 0, the quotient of a and b is defined by the formula a ÷ b = a · (b⁻¹),

where b⁻¹  is the multiplicative inverse of  b.

For example, in the field Z5, we can divide 2 by 3 as  follows:

2 ÷ 3  =  2 · (3⁻¹)  =  2 · 2  = 4.

Now that we have subtraction and division, we can perform almost any algebraic computation in the usual way for elements of a field. :

EXAMPLE 1 : Solving an Equation

Solve the following equation:

3x + 4  ≡ 6 (mod 7).

SOLUTION: Since Z7 is a field, we can solve this equation using elementary algebra. First we subtract 4 from both sides:

3x  ≡ 2(mod 7).

Next we must divide through by 3. A moment’s thought reveals that 3⁻¹ =   5 in Z7, so dividing through by 3 is the same as multiplying through by 5. This gives:

x ≡ 5 · 2 ≡ 3  (mod 7).

8.5 Finite Field in Cryptography:

Finite fields are one of the essential building blocks in coding theory and cryptography and thus appear in many areas in IT security. This section introduces finite fields systematically stating for which orders finite fields exist, shows how to construct them and how to compute in them efficiently. For applications 3 types of fields are particularly interesting – fields with a prime number of elements, extension fields of the minimal field {0, 1} and optimal extension fields.

This section studies polynomials over finite fields.

A polynomial f (x) ∈ K [x] is irreducible if it cannot be written as a product of polynomials of lower degree over the same field, i.e. u(x)|f (x) implies u is constant or u(x) = f (x). Otherwise it is called reducible.

Example : Consider the following polynomials in IF2[x]: f1(x) = x, f2(x) = x2 + 1,f3(x) = x2 + x + 1, and f4(x) = x4 + x2 + 1.

a)   Apparently f1 is irreducible.

b)   A non-trivial factor of f2 must be linear, one sees that (x + 1)|f2(x), actually f2(x) = (x + 1)2.

c)   There are only two linear polynomials, x and x + 1, over IF2. One easily checks that none of them divides f3, so f3 is irreducible.

d)   The last polynomial is not divisible by a linear factor. However, it is not irreducible since f4(x) = (x23 + x + 1)2 = f 2(x). which cannot be

factored further since f3   is8

irreducible.

For functions over the reals, the derivative gives information about the slope of the tangent in a point. In the discrete setting of finite fields we lose this interpretation but we can still define the derivative of a polynomial.

Definition: (Minimal polynomial)

Let K be a field, L be a finite extension field of K and α ∈ L. The polynomial mα ∈ K[x] constructed in Lemma 23 is called the minimal polynomial of α over K.

The prime fields IFp are constructed as residue classes of the integers modulo a prime p. We have seen that the ring of polynomials over a field shares many similarities with the ring of integers and so we consider the polynomial ring modulo an irreducible polynomial.

8.6 Existence and uniqueness of finite fields

We have now obtained a way of constructing finite fields by using irreducible polynomials over prime fields and mentioned that the same construction can also be used for an arbitrary base field. This raises the need to question whether the constructed fields are the same and whether we can always find an irreducible polynomial of the desired degree. This section is rather technical in nature but establishes a major result towards proving the existence and uniqueness of finite fields of prime power order.

The following definition and lemma hold in the context of arbitrary fields.

Definition:(Splitting field)

Let K be a field and let f (x) ∈ K[x] be a polynomial. The splitting field of f is the smallest field extension L of K so that f splits into linear factors in L[x].

We state the following lemma without proof. It is an important piece in the construction of finite fields but its proof is rather technical.

GF(p) of order (that is, size) p is easily constructed as the integers modulo p. The elements of a prime field may be represented by integers in the range 0, …, p − 1.

Let F be a finite field. For any element x in F and any integer n, let us denote by n⋅x the sum of n copies of x. The least positive n such that n⋅1 = 0 must exist and is prime; it is called the characteristic of the field.

If the characteristic of F is p, one can multiply an element k of GF(p) by an element x of F by choosing an integer representative for k. This multiplication makes F into a GF(p)-vector space. It follows that the number of elements of F is p ⁿ for some integer n

For every prime number p and every positive integer n, there are finite fields of order pⁿ, and all fields of this order are isomorphic. One may therefore identify all fields of order pⁿ, which are therefore unambiguously denoted , Fpⁿ or GF(pⁿ), where the letters GF stand for “Galois field”.

The identity

is true (for every x and y) in a field of characteristic p. (This follows from the fact that all, except the first and the last, binomial coefficients of the expansion of (x + y)^p are multiples of p).

For every element x in the prime field GF(p), one has xp = x (This is an immediate consequence of Fermat’s little theorem, and this may be easily proved as follows: the equality is trivially true for x = 0 and x = 1; one obtains the result for the other elements of GF(p) by applying the above identity to x and 1, where x successively takes the values 1, 2, …, p − 1 modulo p.) This implies the equality for polynomials over GF(p). More generally, every element in GF(pⁿ) satisfies the polynomial equation x^pn − x = 0.

Any finite field extension of a finite field is separable and simple. That is, if E is a finite field and F is a subfield of E, then E is obtained from F by adjoining a single element whose minimal polynomial is separable. To use a jargon, finite fields are perfect.

Let q = pⁿ be a prime power, and F be the splitting field of the polynomial over the prime field GF(p). This means that F is a finite field of lowest order, in which P has q distinct roots (the roots are distinct, as the formal derivative of P is equal to −1). Above identity shows that the sum and the product of two roots of P are roots of P, as well as the multiplicative inverse of a root of P. In other word, the roots of P form a field of order q, which is equal to F by the minimality of the splitting field.

The uniqueness up to isomorphism of splitting fields implies thus that all fields of order q are isomorphic.

In summary, we have the following classification theorem first proved in 1893 by E. H. Moore:

The order of a finite field is a prime power. For every prime power q there are fields of order q, and they are all isomorphic. In these fields, every element satisfies and the polynomial Xq − X factors as:

It follows that GF(pn) contains a subfield isomorphic to GF(pm) if and only if m is a divisor of n; in that case, this subfield is unique. In fact, the polynomial Xpm − X divides Xpn − X if and only if m is a divisor of n.

Non-prime fields

Given a prime power q = pⁿ with p prime and n > 1, the field GF(q) may be explicitly constructed in the following way. One chooses first an irreducible polynomial P in GF(p)[X]of degree n (such an irreducible polynomial always exists). Then the quotient ring of the polynomial ring GF(p)[X] by the ideal generated by P is a field of order q.

More explicitly, the elements of GF(q) are the polynomials over GF(p) whose degree is strictly less than n. The addition and the subtraction are those of polynomials over GF(p). The product of two elements is the remainder of the Euclidean division by P of the product in GF(p)[X]. The multiplicative inverse of a non-zero element may be computed with the extended Euclidean algorithm; see Extended Euclidean algorithm § Simple algebraic field extensions.

Except in the construction of GF(4), there are several possible choices for P, which produce isomorphic results. To simplify the Euclidean division, for P one commonly chooses polynomials of the form which make the needed Euclidean divisions very efficient. However, for some fields, typically in characteristic 2, irreducible polynomials of the form Xⁿ + aX + b may not exist. In characteristic 2, if the polynomial Xⁿ + X + 1 is reducible, it is recommended to choose Xⁿ + X ^k + 1 with the lowest possible k that makes the polynomial irreducible. If all these trinomials are reducible, one chooses “pentanomials” X ⁿ + X ^a + X ^b + X ^c + 1, as polynomials of degree
greater than 1, with an even number of terms, are never irreducible in characteristic 2, having 1 as a root. “pentanomials” Xⁿ + X^a + X^b + X^c + 1, as polynomials of degree greater than 1, with an even number of terms, are never irreducible in characteristic 2, having 1 as a root.

Summary

Ø Outlined the algebraic structures

Ø Discussed about the groups, rings and fields with examples.

Ø Discussed about the galois field to perform modulo prime p with some examples.