{"id":84,"date":"2018-07-21T11:06:23","date_gmt":"2018-07-21T11:06:23","guid":{"rendered":"http:\/\/csp11.epgpbooks.inflibnet.ac.in\/?post_type=chapter&p=84"},"modified":"2018-12-27T10:02:31","modified_gmt":"2018-12-27T10:02:31","slug":"algebraic-structures-and-finite-fields-1","status":"publish","type":"chapter","link":"https:\/\/ebooks.inflibnet.ac.in\/csp11\/chapter\/algebraic-structures-and-finite-fields-1\/","title":{"rendered":"Algebraic Structures and Finite Fields 1"},"content":{"raw":"
\"epgp<\/a>\r\n<\/span><\/div>\r\n
\r\n\r\n \r\n\r\n \r\n\r\n \r\n\r\nLearning Objectives<\/strong>\r\n\r\n\u00d8\u00a0 To review the concept of algebraic structures\r\n\r\n\u00d8\u00a0\u00a0 To define and give some examples of groups, rings, fields\r\n\r\n\u00d8\u00a0\u00a0 To review the concept of Ring and Field\r\n\r\n\u00d8\u00a0\u00a0 To define the purpose of Finite Field in\u00a0 cryptography\r\n\r\n\u00d8\u00a0\u00a0 To discuss about the Galois field to perform modulo prime p\r\n\r\n\u00d8\u00a0\u00a0 To understand Galois fields with some examples.\r\n\r\n \r\n\r\n8.1 Algebraic Structures:<\/strong>\r\n\r\n \r\n

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.<\/p>\r\n \r\n\r\n8.2 Group<\/strong>\r\n\r\n \r\n\r\nA group<\/strong> is a set G<\/em> together with a binary operation \u2217<\/em> on G<\/em>, satisfying the following axioms:\r\n\r\n \r\n\r\n1.\u00a0\u00a0\u00a0 The\u00a0 operation\u00a0 \u2217<\/em> is\u00a0 associative.\u00a0 That is,\r\n

a\u00a0 <\/em>\u2217<\/em> (b<\/em> \u2217<\/em> c<\/em>) = (a<\/em> \u2217<\/em> b<\/em>) \u2217<\/em> c<\/em> for all a, b, c<\/em> \u2208<\/em> G<\/em>.<\/p>\r\n\u00a0<\/em>\r\n\r\n2.\u00a0\u00a0\u00a0 There exists an element e<\/em> \u2208<\/em> G<\/em> with the property that\r\n

a <\/em>\u2217<\/em> e <\/em>= e <\/em>\u2217<\/em> a <\/em>= a<\/em><\/p>\r\n\r\n<\/div>\r\n\u00a0 \u00a0for all <\/span>a<\/em> \u2208<\/em> G<\/em>. (This element <\/span>e<\/em> is called the <\/span>identity element<\/strong> of <\/span>G<\/em>.)<\/span>\r\n

\r\n\r\n3.\u00a0\u00a0\u00a0 For each element a<\/em> \u2208<\/em> G<\/em>, there exists an element a<\/em>\u2212<\/em>1 \u2208<\/em> G<\/em> such that\r\n\r\n \r\n

a\u00a0\u00a0 <\/em>\u2217<\/em> .a<\/em>\u2212<\/em>1<\/sup>. = .a<\/em>\u2212<\/em>1<\/sup>. \u2217<\/em> a<\/em><\/p>\r\n

=\u00a0\u00a0\u00a0 e.<\/em><\/p>\r\n \r\n\r\n(The element a<\/em>\u2212<\/em>1<\/sup>\u00a0 is called the inverse<\/strong> of a<\/em>.)\r\n\r\n \r\n

The binary operation \u2217<\/em> 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:<\/p>\r\n \r\n

\u2022\u00a0 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.<\/p>\r\n \r\n

\u2022\u00a0 The set R \u2212<\/em> {<\/em>0}<\/em> 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.<\/p>\r\n \r\n

\u2022\u00a0 The set GL(n,<\/em> R) of all invertible n \u00d7 n<\/em> matrices forms a group under the operation of matrix multiplication. In this case, the identity element is the<\/p>\r\n\u00a0<\/em>\r\n\r\nn \u00d7 n <\/em>identity matrix.\r\n\r\n \r\n

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.<\/p>\r\n \r\n\r\nHere is a partial list of the most important algebraic\u00a0\u00a0\u00a0\u00a0 structures:\r\n\r\n \r\n

\u2022\u00a0 A group<\/strong> 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.<\/p>\r\n\u00a0<\/em>\r\n

\u2022\u00a0 A field<\/strong> 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.<\/p>\r\n\u00a0<\/em>\r\n

\u2022\u00a0 A ring<\/strong> 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\u00d7 n\u00a0<\/em>matrices under the operations of matrix addition and matrix multiplication. The integers Z also form a ring under the operations of addition\u00a0<\/span>and multiplication.<\/span><\/p>\r\n\r\n<\/div>\r\n

\r\n\r\n \r\n

\u2022\u00a0 A module<\/strong> is similar to a vector space, except that the scalars are only required to be elements of a ring. For example, the set Zn<\/em> of n<\/em>-dimensional vectors with integer entries forms a module, where \u201cscalar multiplication\u201d refers to multiplication by integer scalars.<\/p>\r\n \r\n

Because algebraic structures are inherently abstract, the names for them are fairly arbitrary. Words like \u201cgroup\u201d, \u201cmodule\u201d, and \u201cfield\u201d are just interchangeable collective nouns, and you should not ascribe any importance to which structure has which name. The word \u201cring\u201d is also in this category\u2014it 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.<\/p>\r\n \r\n

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.<\/p>\r\n \r\n\r\n \r\n\r\n \r\n\r\n8.3 Fields<\/strong>\r\n\r\n \r\n

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.<\/p>\r\n \r\n

A field<\/strong> is a set F<\/em> together with two binary operations + (the addition<\/strong> operation<\/strong>) and (the multiplication operation<\/strong>), that satisfy the following axioms:<\/p>\r\n \r\n\r\n \r\n\r\nThe addition operation is associative.\u00a0 That is,\r\n

a + (b + c) = (a + b) + c<\/p>\r\nfor all a, b,c\u00a0 \u2208 F .\r\n\r\n<\/div>\r\n \r\n

\r\n\r\nThe addition operation is commutative.\u00a0 That is,\r\n

a + b = b + a ,for all a,b \u2208 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 \u2208 F<\/p>\r\n \r\n\r\n \r\n\r\ni.\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 For each element a<\/em> \u2208<\/em> F<\/em> , there is an element \u2212a<\/em> \u2208<\/em> F<\/em> , called the additive inverse <\/strong>of a<\/em>, with the property that\r\n\r\na\u00a0\u00a0 <\/em>+ (\u2212a<\/em>) =\u00a0 0.<\/em>\r\n\r\nii. The multiplication operation is associative. That is,\r\n\r\na \u00b7 <\/em>(b \u00b7 c<\/em>) = (a \u00b7 b<\/em>) \u00b7 c<\/em>\r\n\r\nfor all a, b, c<\/em> \u2208<\/em> F<\/em> .\r\n\r\n \r\n\r\niii.\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 The multiplication operation is commutative. That is,\r\n\r\na \u00b7 b <\/em>= b \u00b7 a<\/em>\r\n\r\nfor all a, b<\/em> \u2208<\/em> F<\/em> .\r\n\r\n \r\n\r\niv.\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 There exists a special element of F<\/em> called the multiplicative<\/strong> identity<\/strong>, denoted by the symbol 1.This element has the property that\r\n\r\n \r\n\r\na \u00b7 <\/em>1 = a<\/em>\r\n\r\n<\/div>\r\n

\r\n\r\nfor all a<\/em> \u2208<\/em> F<\/em> .\r\n\r\n \r\n

v.\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 For each element a<\/em> \u2208<\/em> F<\/em> other than 0, there exists an element a<\/em>\u2212<\/em>1\u00a0 \u2208\u00a0<\/em>F <\/em>, called\u00a0 the multiplicative\u00a0 inverse<\/strong> of a<\/em>, with the property\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 that<\/p>\r\n \r\n\r\na\u00a0\u00a0\u00a0 <\/em>\u00b7 a<\/em>\u2212<\/em>1 = 1.<\/em>\r\n\r\n \r\n\r\nvi.\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 The multiplication operation distributes over the addition operation. That is,\r\n\r\n \r\n\r\na\u00a0\u00a0 <\/em>\u00b7 <\/em>(b <\/em>+ c<\/em>) = (a \u00b7 b<\/em>) +(ac<\/em>)\r\n\r\n \r\n\r\nfor all a, b, c<\/em> \u2208<\/em> F<\/em> .\r\n\r\n \r\n\r\n \r\n

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\u00a0with a few other examples:<\/p>\r\n\r\n<\/div>\r\n

\r\n\r\n \r\n\r\n \r\n

\u2022\u00a0 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.<\/p>\r\n\u00a0<\/em>\r\n

\u2022\u00a0 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.<\/p>\r\n \r\n\r\nThe following example discusses another class of fields that we shall be using repeatedly.\r\n\r\n \r\n\r\n \r\n\r\nEXAMPLE 1 <\/strong>Integers Modulo n<\/em>\r\n\r\n \r\n\r\nIf n \u2265<\/em> 2, let Zn<\/em> denote the set {<\/em>0,<\/em> 1, . . . , n \u2212<\/em> 1}<\/em> under the operations of addition\r\n\r\n \r\n\r\nand multiplication modulo n<\/em> . For example, here are the addition and multiplication tables for Z5<\/sub>:\r\n\r\n \r\n\r\n\"\"\r\n

It is not hard to see that Zn<\/em> satisfies most of the axioms for a field, but it is not clear that every nonzero element of Z n<\/em> 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,<\/p>\r\n \r\n\r\n1\u2212<\/em>1<\/sup> = 1,<\/em> 2\u2212<\/em>1<\/sup> = 3,<\/em> 3\u2212<\/em>1<\/sup> = 2,<\/em> and 4\u2212<\/em>1<\/sup> = 4,<\/em> Thus Z5<\/sub> is a field.\r\n\r\n \r\n\r\n \r\n\r\nThe same is not true for Z6. Here is the multiplication table modulo\u00a0 6:\r\n\r\n<\/div>\r\n \r\n

\r\n\r\n\"\"\r\n\r\n \r\n\r\n \r\n\r\nAs you can see from this table, 1\u2212<\/em>1<\/sup> = 1 and 5\u2212<\/em>1<\/sup> = 5 in Z6, but the elements 2, 3, and 4 do not have multiplicative inverses.\r\n\r\n \r\n

The following theorem from number theory characterizes which elements have multiplicative inverses. We will not prove this theorem here:<\/p>\r\n \r\n\r\nLet <\/em>n<\/em> \u2208<\/em> N, and let <\/em>k<\/em> \u2208<\/em> Zn<\/em>. Then <\/em>k<\/em> has a multiplicative inverse in <\/em>Zn<\/em> if and only if <\/em>k<\/em> and <\/em>n<\/em> are relatively prime.<\/em>\r\n\r\n \r\n\r\n \r\n\r\nTheorem 1<\/strong>\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 Multiplicative Inverses in Zn<\/em>\r\n\r\n \r\n

Here relatively prime<\/strong> means that k<\/em> and n<\/em> have no common prime factors, their greatest common divisor is 1. This explains why 2, 3, and 4 have no multiplicative inverses in Z6 \u2014 all of these numbers have a factor in common with 6. We can immediately conclude the following:<\/p>\r\n \r\n\r\nZn<\/em>\u00a0 is a field if and only if<\/em>\u00a0 n<\/em> is\u00a0 prime.<\/em>\r\n\r\n \r\n\r\n \r\n\r\nCorollary 2<\/strong>\u00a0\u00a0 Prime Fields:\r\n\r\n \r\n

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:<\/p>\r\n \r\n\r\n\"\"\r\n\r\n<\/div>\r\n\"\"<\/em>\r\n

\r\n\r\n \r\n\r\n \r\n

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.<\/p>\r\n \r\n

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<\/em> elements if and only if n<\/em> is a power of a prime.<\/p>\r\n \r\n\r\n \r\n\r\n \r\n\r\n8.4 Algebra of Fields<\/strong>\r\n\r\n \r\n

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.<\/p>\r\n \r\n

Of course, the definition of a field involves only addition and multiplication, but we usually think of algebra as involving the four<\/em> operations of addition, subtraction, multiplication, and division. Fortunately, it is not difficult to define subtraction and division for elements of a field.<\/p>\r\n \r\n\r\n \r\n\r\n \r\n\r\nDefinition: Subtraction and Division in Fields <\/strong>Let F<\/em> be a field, and let a, b<\/em> \u2208<\/em> F<\/em> .\r\n\r\n(a) The difference<\/strong> of a<\/em> and b<\/em> is defined by the\u00a0 formula\r\n

a\u00a0\u00a0 <\/em>\u2212 b <\/em>= a <\/em>+ (\u2212b<\/em>),<\/em><\/p>\r\nwhere \u2212b<\/em> is the additive inverse of\u00a0\u00a0\u00a0\u00a0 b<\/em>.\r\n\r\n \r\n\r\n(b)\u00a0\u00a0\u00a0\u00a0 If b<\/em> \u0192<\/em>= 0, the quotient<\/strong> of a<\/em> and b<\/em> is defined by the formula a \u00f7 b <\/em>= a \u00b7 <\/em>(b<\/em>\u2212<\/em>1<\/sup>),<\/em>\r\n

where b<\/em>\u2212<\/em>1<\/sup>\u00a0 is the multiplicative inverse of\u00a0 b<\/em>.<\/p>\r\n \r\n\r\nFor example, in the field Z5, we can divide 2 by 3 as\u00a0 follows:\r\n\r\n \r\n\r\n2 \u00f7<\/em> 3\u00a0 =\u00a0 2 \u00b7<\/em> (3\u2212<\/em>1<\/sup>)\u00a0 =\u00a0 2 \u00b7<\/em> 2\u00a0 = 4.<\/em>\r\n\r\n<\/div>\r\n

\r\n

Now that we have subtraction and division, we can perform almost any algebraic computation in the usual way for elements of a field. :<\/p>\r\n \r\n\r\nEXAMPLE 1 : <\/strong>Solving an Equation\r\n\r\n \r\n\r\nSolve the following equation:\r\n\r\n \r\n\r\n3x<\/em> + 4\u00a0\u00a0\u2261 <\/em>6 (mod 7).<\/em>\r\n\r\n \r\n

SOLUTION: Since Z7 is a field, we can solve this equation using elementary algebra. First we subtract 4 from both sides:<\/p>\r\n \r\n\r\n3x<\/em>\u00a0 \u2261<\/em> 2(mod 7).<\/em>\r\n\r\n \r\n\r\nNext we must divide through by 3. A moment\u2019s thought reveals that 3\u2212<\/em>1<\/sup> =\u00a0\u00a0 5 in Z7, so dividing through by 3 is the same as multiplying through by 5. This gives:\r\n\r\n \r\n

x\u00a0<\/em>\u2261 <\/em>5 \u00b7 <\/em>2 \u2261 <\/em>3\u00a0 (mod 7).<\/em><\/p>\r\n \r\n\r\n8.5 Finite Field in Cryptography:<\/strong>\r\n\r\n \r\n

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 \u2013 fields with a prime number of elements, extension fields of the minimal field {0, 1} and optimal extension fields.<\/p>\r\n \r\n\r\nThis section studies polynomials over finite fields.\r\n\r\n \r\n

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

Example : <\/strong>Consider the following polynomials in IF2[x<\/em>]: f<\/em>1(x<\/em>) = x, f<\/em>2(x<\/em>) = x<\/em>2 + 1,f<\/em>3(x<\/em>) = x<\/em>2 + x <\/em>+ 1, and f<\/em>4(x<\/em>) = x<\/em>4 + x<\/em>2 + 1.<\/em><\/p>\r\n \r\n\r\na)\u00a0\u00a0 <\/em>Apparently f1 is irreducible.\r\n\r\n \r\n\r\nb)\u00a0\u00a0 <\/em>A non-trivial factor of f2 must be linear, one sees that (x + 1)|f2(x), actually f2(x) = (x + 1)2.\r\n\r\n\u00a0<\/em>\r\n

c)\u00a0\u00a0 <\/em>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.<\/p>\r\n \r\n

d)\u00a0\u00a0 <\/em>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<\/p>\r\nfactored further since f3\u00a0\u00a0 is8\r\n\r\nirreducible.\r\n\r\n<\/div>\r\n

\r\n

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.<\/p>\r\n \r\n\r\nDefinition: (Minimal polynomial)<\/strong>\r\n\r\n \r\n

Let K be a field, L be a finite extension field of K and \u03b1 \u2208 L. The polynomial m\u03b1 \u2208 K[x] constructed in Lemma 23 is called the minimal polynomial of \u03b1 over K.<\/p>\r\n \r\n

The prime fields IFp<\/em> are constructed as residue classes of the integers modulo a prime p<\/em>. 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.<\/p>\r\n \r\n\r\n\"\"\r\n\r\n<\/div>\r\n

\r\n\r\n \r\n\r\n8.6 Existence and uniqueness of finite fields<\/strong>\r\n\r\n \r\n

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.<\/p>\r\n \r\n\r\nThe following definition and lemma hold in the context of arbitrary fields.\r\n\r\n \r\n\r\n \r\n\r\nDefinition:(Splitting field)<\/strong>\r\n\r\n \r\n

Let K be a field and let f <\/em>(x<\/em>) \u2208<\/em> K<\/em>[x<\/em>] be a polynomial. The <\/em>splitting field of f is the smallest field extension L of K so that f splits into linear factors in L<\/em>[x<\/em>].<\/em><\/p>\r\n \r\n\r\n \r\n

We state the following lemma without proof. It is an important piece in the construction of finite fields but its proof is rather technical.<\/p>\r\n \r\n

GF(p<\/em>) of order (that is, size) p<\/em> is easily constructed as the integers modulo p<\/em>.\u00a0<\/a>The elements of a prime field may be represented by integers in the range 0, ..., p<\/em> \u2212 1.<\/p>\r\n \r\n

Let F<\/em> be a finite field. For any element x<\/em> in F<\/em> and any integer <\/a>n<\/em>, let us denote by n<\/em>\u22c5x<\/em> the sum of n<\/em> copies of x<\/em>. The least positive n<\/em> such that n<\/em>\u22c51 = 0 must exist and is prime; it is called the characteristic <\/a>of the field.<\/p>\r\n\r\n<\/div>\r\n

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 n\u00a0<\/sup>for some integer n<\/p>\r\n\r\n

\r\n\r\n \r\n

For every prime number p<\/em> and every positive integer n<\/em>, there are finite fields of order p<\/em>n<\/em><\/sup>, and all fields of this order are isomorphic. <\/a>One may therefore identify all fields of order p<\/em>n<\/em><\/sup>, which are therefore unambiguously denoted , F<\/strong>p<\/em>n<\/em><\/sup> or GF(p<\/em>n<\/em><\/sup>), where the letters GF stand for \"Galois field\".<\/p>\r\n \r\n\r\nThe identity\r\n\r\n \r\n

is true (for every x<\/em> and y<\/em>) in a field of characteristic p<\/em>. (This follows from the fact that all, except the first and the last, binomial coefficients <\/a>of the expansion of (x<\/em> + y<\/em>)p<\/em><\/sup> are multiples of p<\/em>).<\/p>\r\n \r\n\r\n \r\n

For every element x<\/em> in the prime field GF(p<\/em>), one has x<\/em>p<\/em> = x<\/em> (This is an immediate consequence of Fermat's little theorem, <\/a>and this may be easily\u00a0proved as follows: the equality is trivially true for <\/span>x<\/em> = 0 and <\/span>x<\/em> = 1; one obtains the result for the other elements of GF(<\/span>p<\/em>) by applying the above identity to <\/span>x<\/em> and 1, where <\/span>x<\/em> successively takes the values 1, 2, ..., <\/span>p<\/em> \u2212 1 modulo <\/span>p<\/em>.) This implies the equality for polynomials over GF(<\/span>p<\/em>). More generally, every element in GF(<\/span>p<\/em>n<\/em><\/sup>) satisfies the polynomial equation <\/span>x<\/em>pn<\/em><\/sup> \u2212 <\/span>x<\/em> = 0.<\/span><\/p>\r\n\r\n<\/div>\r\n

\r\n\r\n \r\n

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

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

The uniqueness up to isomorphism of splitting fields implies thus that all fields of order q<\/em> are isomorphic.<\/p>\r\n \r\n\r\nIn summary, we have the following classification theorem first proved in 1893 by E. H. Moore:<\/a>\r\n\r\n \r\n

The order of a finite field is a prime power. For every prime power q there are fields of order q<\/em>, and they are all isomorphic. In these fields, every element satisfies and the polynomial X<\/em>q<\/em> \u2212 X factors as<\/em>:<\/p>\r\n \r\n

It follows that GF(p<\/em>n<\/em>) contains a subfield isomorphic to GF(p<\/em>m<\/em>) if and only if m<\/em> is a divisor of n<\/em>; in that case, this subfield is unique. In fact, the polynomial X<\/em>pm<\/em> \u2212 X<\/em> divides X<\/em>pn<\/em> \u2212 X<\/em> if and only if m<\/em> is a divisor of n<\/em>.<\/p>\r\n \r\n\r\nNon-prime fields<\/strong>\r\n\r\n \r\n

Given a prime power q = pn<\/sup> 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.<\/p>\r\n \r\n

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

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 Xn<\/sup> + aX + b may not exist. In characteristic 2, if the polynomial Xn<\/sup> + X + 1 is reducible, it is recommended to choose Xn<\/sup> + X k<\/sup> + 1 with the lowest possible k that makes the polynomial irreducible. If all these trinomials are reducible, one chooses \"pentanomials\" X n<\/sup> + X a<\/sup> + X b<\/sup> + X c<\/sup> + 1, as polynomials of degree\r\ngreater than 1, with an even number of terms, are never irreducible in characteristic 2, having 1 as a root. \"pentanomials\" X<\/em>n<\/em><\/sup> + X<\/em>a<\/em><\/sup> + X<\/em>b<\/em><\/sup> + X<\/em>c<\/em><\/sup> + 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.<\/p>\r\n \r\n\r\n \r\n\r\n \r\n\r\nSummary<\/strong>\r\n\r\n \r\n\r\n\u00d8 Outlined the algebraic structures\r\n\r\n\u00d8 Discussed about the groups, rings and fields with examples.\r\n\r\n\u00d8 Discussed about the galois field to perform modulo prime p with some examples.\r\n\r\n\r\n\r\n\r\n
you can view video on Algebraic Structures and Finite Fields 1<\/strong><\/td>\r\n\"\"<\/a><\/td>\r\n<\/tr>\r\n<\/tbody>\r\n<\/table>\r\n\r\n\"\"","rendered":"
\"epgp<\/a>
\n<\/span><\/div>\n
\n

 <\/p>\n

 <\/p>\n

 <\/p>\n

Learning Objectives<\/strong><\/p>\n

\u00d8\u00a0 To review the concept of algebraic structures<\/p>\n

\u00d8\u00a0\u00a0 To define and give some examples of groups, rings, fields<\/p>\n

\u00d8\u00a0\u00a0 To review the concept of Ring and Field<\/p>\n

\u00d8\u00a0\u00a0 To define the purpose of Finite Field in\u00a0 cryptography<\/p>\n

\u00d8\u00a0\u00a0 To discuss about the Galois field to perform modulo prime p<\/p>\n

\u00d8\u00a0\u00a0 To understand Galois fields with some examples.<\/p>\n

 <\/p>\n

8.1 Algebraic Structures:<\/strong><\/p>\n

 <\/p>\n

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.<\/p>\n

 <\/p>\n

8.2 Group<\/strong><\/p>\n

 <\/p>\n

A group<\/strong> is a set G<\/em> together with a binary operation \u2217<\/em> on G<\/em>, satisfying the following axioms:<\/p>\n

 <\/p>\n

1.\u00a0\u00a0\u00a0 The\u00a0 operation\u00a0 \u2217<\/em> is\u00a0 associative.\u00a0 That is,<\/p>\n

a\u00a0 <\/em>\u2217<\/em> (b<\/em> \u2217<\/em> c<\/em>) = (a<\/em> \u2217<\/em> b<\/em>) \u2217<\/em> c<\/em> for all a, b, c<\/em> \u2208<\/em> G<\/em>.<\/p>\n

\u00a0<\/em><\/p>\n

2.\u00a0\u00a0\u00a0 There exists an element e<\/em> \u2208<\/em> G<\/em> with the property that<\/p>\n

a <\/em>\u2217<\/em> e <\/em>= e <\/em>\u2217<\/em> a <\/em>= a<\/em><\/p>\n<\/div>\n

\u00a0 \u00a0for all <\/span>a<\/em> \u2208<\/em> G<\/em>. (This element <\/span>e<\/em> is called the <\/span>identity element<\/strong> of <\/span>G<\/em>.)<\/span><\/p>\n

\n

3.\u00a0\u00a0\u00a0 For each element a<\/em> \u2208<\/em> G<\/em>, there exists an element a<\/em>\u2212<\/em>1 \u2208<\/em> G<\/em> such that<\/p>\n

 <\/p>\n

a\u00a0\u00a0 <\/em>\u2217<\/em> .a<\/em>\u2212<\/em>1<\/sup>. = .a<\/em>\u2212<\/em>1<\/sup>. \u2217<\/em> a<\/em><\/p>\n

=\u00a0\u00a0\u00a0 e.<\/em><\/p>\n

 <\/p>\n

(The element a<\/em>\u2212<\/em>1<\/sup>\u00a0 is called the inverse<\/strong> of a<\/em>.)<\/p>\n

 <\/p>\n

The binary operation \u2217<\/em> 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:<\/p>\n

 <\/p>\n

\u2022\u00a0 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.<\/p>\n

 <\/p>\n

\u2022\u00a0 The set R \u2212<\/em> {<\/em>0}<\/em> 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.<\/p>\n

 <\/p>\n

\u2022\u00a0 The set GL(n,<\/em> R) of all invertible n \u00d7 n<\/em> matrices forms a group under the operation of matrix multiplication. In this case, the identity element is the<\/p>\n

\u00a0<\/em><\/p>\n

n \u00d7 n <\/em>identity matrix.<\/p>\n

 <\/p>\n

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.<\/p>\n

 <\/p>\n

Here is a partial list of the most important algebraic\u00a0\u00a0\u00a0\u00a0 structures:<\/p>\n

 <\/p>\n

\u2022\u00a0 A group<\/strong> 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.<\/p>\n

\u00a0<\/em><\/p>\n

\u2022\u00a0 A field<\/strong> 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.<\/p>\n

\u00a0<\/em><\/p>\n

\u2022\u00a0 A ring<\/strong> 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\u00d7 n\u00a0<\/em>matrices under the operations of matrix addition and matrix multiplication. The integers Z also form a ring under the operations of addition\u00a0<\/span>and multiplication.<\/span><\/p>\n<\/div>\n

\n

 <\/p>\n

\u2022\u00a0 A module<\/strong> is similar to a vector space, except that the scalars are only required to be elements of a ring. For example, the set Zn<\/em> of n<\/em>-dimensional vectors with integer entries forms a module, where \u201cscalar multiplication\u201d refers to multiplication by integer scalars.<\/p>\n

 <\/p>\n

Because algebraic structures are inherently abstract, the names for them are fairly arbitrary. Words like \u201cgroup\u201d, \u201cmodule\u201d, and \u201cfield\u201d are just interchangeable collective nouns, and you should not ascribe any importance to which structure has which name. The word \u201cring\u201d is also in this category\u2014it 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.<\/p>\n

 <\/p>\n

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.<\/p>\n

 <\/p>\n

 <\/p>\n

 <\/p>\n

8.3 Fields<\/strong><\/p>\n

 <\/p>\n

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.<\/p>\n

 <\/p>\n

A field<\/strong> is a set F<\/em> together with two binary operations + (the addition<\/strong> operation<\/strong>) and (the multiplication operation<\/strong>), that satisfy the following axioms:<\/p>\n

 <\/p>\n

 <\/p>\n

The addition operation is associative.\u00a0 That is,<\/p>\n

a + (b + c) = (a + b) + c<\/p>\n

for all a, b,c\u00a0 \u2208 F .<\/p>\n<\/div>\n

 <\/p>\n

\n

The addition operation is commutative.\u00a0 That is,<\/p>\n

a + b = b + a ,for all a,b \u2208 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 \u2208 F<\/p>\n

 <\/p>\n

 <\/p>\n

i.\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 For each element a<\/em> \u2208<\/em> F<\/em> , there is an element \u2212a<\/em> \u2208<\/em> F<\/em> , called the additive inverse <\/strong>of a<\/em>, with the property that<\/p>\n

a\u00a0\u00a0 <\/em>+ (\u2212a<\/em>) =\u00a0 0.<\/em><\/p>\n

ii. The multiplication operation is associative. That is,<\/p>\n

a \u00b7 <\/em>(b \u00b7 c<\/em>) = (a \u00b7 b<\/em>) \u00b7 c<\/em><\/p>\n

for all a, b, c<\/em> \u2208<\/em> F<\/em> .<\/p>\n

 <\/p>\n

iii.\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 The multiplication operation is commutative. That is,<\/p>\n

a \u00b7 b <\/em>= b \u00b7 a<\/em><\/p>\n

for all a, b<\/em> \u2208<\/em> F<\/em> .<\/p>\n

 <\/p>\n

iv.\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 There exists a special element of F<\/em> called the multiplicative<\/strong> identity<\/strong>, denoted by the symbol 1.This element has the property that<\/p>\n

 <\/p>\n

a \u00b7 <\/em>1 = a<\/em><\/p>\n<\/div>\n

\n

for all a<\/em> \u2208<\/em> F<\/em> .<\/p>\n

 <\/p>\n

v.\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 For each element a<\/em> \u2208<\/em> F<\/em> other than 0, there exists an element a<\/em>\u2212<\/em>1\u00a0 \u2208\u00a0<\/em>F <\/em>, called\u00a0 the multiplicative\u00a0 inverse<\/strong> of a<\/em>, with the property\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 that<\/p>\n

 <\/p>\n

a\u00a0\u00a0\u00a0 <\/em>\u00b7 a<\/em>\u2212<\/em>1 = 1.<\/em><\/p>\n

 <\/p>\n

vi.\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 The multiplication operation distributes over the addition operation. That is,<\/p>\n

 <\/p>\n

a\u00a0\u00a0 <\/em>\u00b7 <\/em>(b <\/em>+ c<\/em>) = (a \u00b7 b<\/em>) +(ac<\/em>)<\/p>\n

 <\/p>\n

for all a, b, c<\/em> \u2208<\/em> F<\/em> .<\/p>\n

 <\/p>\n

 <\/p>\n

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\u00a0with a few other examples:<\/p>\n<\/div>\n

\n

 <\/p>\n

 <\/p>\n

\u2022\u00a0 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.<\/p>\n

\u00a0<\/em><\/p>\n

\u2022\u00a0 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.<\/p>\n

 <\/p>\n

The following example discusses another class of fields that we shall be using repeatedly.<\/p>\n

 <\/p>\n

 <\/p>\n

EXAMPLE 1 <\/strong>Integers Modulo n<\/em><\/p>\n

 <\/p>\n

If n \u2265<\/em> 2, let Zn<\/em> denote the set {<\/em>0,<\/em> 1, . . . , n \u2212<\/em> 1}<\/em> under the operations of addition<\/p>\n

 <\/p>\n

and multiplication modulo n<\/em> . For example, here are the addition and multiplication tables for Z5<\/sub>:<\/p>\n

 <\/p>\n

\"\"<\/p>\n

It is not hard to see that Zn<\/em> satisfies most of the axioms for a field, but it is not clear that every nonzero element of Z n<\/em> 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,<\/p>\n

 <\/p>\n

1\u2212<\/em>1<\/sup> = 1,<\/em> 2\u2212<\/em>1<\/sup> = 3,<\/em> 3\u2212<\/em>1<\/sup> = 2,<\/em> and 4\u2212<\/em>1<\/sup> = 4,<\/em> Thus Z5<\/sub> is a field.<\/p>\n

 <\/p>\n

 <\/p>\n

The same is not true for Z6. Here is the multiplication table modulo\u00a0 6:<\/p>\n<\/div>\n

 <\/p>\n

\n

\"\"<\/p>\n

 <\/p>\n

 <\/p>\n

As you can see from this table, 1\u2212<\/em>1<\/sup> = 1 and 5\u2212<\/em>1<\/sup> = 5 in Z6, but the elements 2, 3, and 4 do not have multiplicative inverses.<\/p>\n

 <\/p>\n

The following theorem from number theory characterizes which elements have multiplicative inverses. We will not prove this theorem here:<\/p>\n

 <\/p>\n

Let <\/em>n<\/em> \u2208<\/em> N, and let <\/em>k<\/em> \u2208<\/em> Zn<\/em>. Then <\/em>k<\/em> has a multiplicative inverse in <\/em>Zn<\/em> if and only if <\/em>k<\/em> and <\/em>n<\/em> are relatively prime.<\/em><\/p>\n

 <\/p>\n

 <\/p>\n

Theorem 1<\/strong>\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 Multiplicative Inverses in Zn<\/em><\/p>\n

 <\/p>\n

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

 <\/p>\n

Zn<\/em>\u00a0 is a field if and only if<\/em>\u00a0 n<\/em> is\u00a0 prime.<\/em><\/p>\n

 <\/p>\n

 <\/p>\n

Corollary 2<\/strong>\u00a0\u00a0 Prime Fields:<\/p>\n

 <\/p>\n

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:<\/p>\n

 <\/p>\n

\"\"<\/p>\n<\/div>\n

\"\"<\/em><\/p>\n

\n

 <\/p>\n

 <\/p>\n

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.<\/p>\n

 <\/p>\n

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<\/em> elements if and only if n<\/em> is a power of a prime.<\/p>\n

 <\/p>\n

 <\/p>\n

 <\/p>\n

8.4 Algebra of Fields<\/strong><\/p>\n

 <\/p>\n

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.<\/p>\n

 <\/p>\n

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

 <\/p>\n

 <\/p>\n

 <\/p>\n

Definition: Subtraction and Division in Fields <\/strong>Let F<\/em> be a field, and let a, b<\/em> \u2208<\/em> F<\/em> .<\/p>\n

(a) The difference<\/strong> of a<\/em> and b<\/em> is defined by the\u00a0 formula<\/p>\n

a\u00a0\u00a0 <\/em>\u2212 b <\/em>= a <\/em>+ (\u2212b<\/em>),<\/em><\/p>\n

where \u2212b<\/em> is the additive inverse of\u00a0\u00a0\u00a0\u00a0 b<\/em>.<\/p>\n

 <\/p>\n

(b)\u00a0\u00a0\u00a0\u00a0 If b<\/em> \u0192<\/em>= 0, the quotient<\/strong> of a<\/em> and b<\/em> is defined by the formula a \u00f7 b <\/em>= a \u00b7 <\/em>(b<\/em>\u2212<\/em>1<\/sup>),<\/em><\/p>\n

where b<\/em>\u2212<\/em>1<\/sup>\u00a0 is the multiplicative inverse of\u00a0 b<\/em>.<\/p>\n

 <\/p>\n

For example, in the field Z5, we can divide 2 by 3 as\u00a0 follows:<\/p>\n

 <\/p>\n

2 \u00f7<\/em> 3\u00a0 =\u00a0 2 \u00b7<\/em> (3\u2212<\/em>1<\/sup>)\u00a0 =\u00a0 2 \u00b7<\/em> 2\u00a0 = 4.<\/em><\/p>\n<\/div>\n

\n

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

 <\/p>\n

EXAMPLE 1 : <\/strong>Solving an Equation<\/p>\n

 <\/p>\n

Solve the following equation:<\/p>\n

 <\/p>\n

3x<\/em> + 4\u00a0\u00a0\u2261 <\/em>6 (mod 7).<\/em><\/p>\n

 <\/p>\n

SOLUTION: Since Z7 is a field, we can solve this equation using elementary algebra. First we subtract 4 from both sides:<\/p>\n

 <\/p>\n

3x<\/em>\u00a0 \u2261<\/em> 2(mod 7).<\/em><\/p>\n

 <\/p>\n

Next we must divide through by 3. A moment\u2019s thought reveals that 3\u2212<\/em>1<\/sup> =\u00a0\u00a0 5 in Z7, so dividing through by 3 is the same as multiplying through by 5. This gives:<\/p>\n

 <\/p>\n

x\u00a0<\/em>\u2261 <\/em>5 \u00b7 <\/em>2 \u2261 <\/em>3\u00a0 (mod 7).<\/em><\/p>\n

 <\/p>\n

8.5 Finite Field in Cryptography:<\/strong><\/p>\n

 <\/p>\n

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 \u2013 fields with a prime number of elements, extension fields of the minimal field {0, 1} and optimal extension fields.<\/p>\n

 <\/p>\n

This section studies polynomials over finite fields.<\/p>\n

 <\/p>\n

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

 <\/p>\n

Example : <\/strong>Consider the following polynomials in IF2[x<\/em>]: f<\/em>1(x<\/em>) = x, f<\/em>2(x<\/em>) = x<\/em>2 + 1,f<\/em>3(x<\/em>) = x<\/em>2 + x <\/em>+ 1, and f<\/em>4(x<\/em>) = x<\/em>4 + x<\/em>2 + 1.<\/em><\/p>\n

 <\/p>\n

a)\u00a0\u00a0 <\/em>Apparently f1 is irreducible.<\/p>\n

 <\/p>\n

b)\u00a0\u00a0 <\/em>A non-trivial factor of f2 must be linear, one sees that (x + 1)|f2(x), actually f2(x) = (x + 1)2.<\/p>\n

\u00a0<\/em><\/p>\n

c)\u00a0\u00a0 <\/em>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.<\/p>\n

 <\/p>\n

d)\u00a0\u00a0 <\/em>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<\/p>\n

factored further since f3\u00a0\u00a0 is8<\/p>\n

irreducible.<\/p>\n<\/div>\n

\n

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.<\/p>\n

 <\/p>\n

Definition: (Minimal polynomial)<\/strong><\/p>\n

 <\/p>\n

Let K be a field, L be a finite extension field of K and \u03b1 \u2208 L. The polynomial m\u03b1 \u2208 K[x] constructed in Lemma 23 is called the minimal polynomial of \u03b1 over K.<\/p>\n

 <\/p>\n

The prime fields IFp<\/em> are constructed as residue classes of the integers modulo a prime p<\/em>. 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.<\/p>\n

 <\/p>\n

\"\"<\/p>\n<\/div>\n

\n

 <\/p>\n

8.6 Existence and uniqueness of finite fields<\/strong><\/p>\n

 <\/p>\n

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.<\/p>\n

 <\/p>\n

The following definition and lemma hold in the context of arbitrary fields.<\/p>\n

 <\/p>\n

 <\/p>\n

Definition:(Splitting field)<\/strong><\/p>\n

 <\/p>\n

Let K be a field and let f <\/em>(x<\/em>) \u2208<\/em> K<\/em>[x<\/em>] be a polynomial. The <\/em>splitting field of f is the smallest field extension L of K so that f splits into linear factors in L<\/em>[x<\/em>].<\/em><\/p>\n

 <\/p>\n

 <\/p>\n

We state the following lemma without proof. It is an important piece in the construction of finite fields but its proof is rather technical.<\/p>\n

 <\/p>\n

GF(p<\/em>) of order (that is, size) p<\/em> is easily constructed as the integers modulo p<\/em>.\u00a0<\/a>The elements of a prime field may be represented by integers in the range 0, …, p<\/em> \u2212 1.<\/p>\n

 <\/p>\n

Let F<\/em> be a finite field. For any element x<\/em> in F<\/em> and any integer <\/a>n<\/em>, let us denote by n<\/em>\u22c5x<\/em> the sum of n<\/em> copies of x<\/em>. The least positive n<\/em> such that n<\/em>\u22c51 = 0 must exist and is prime; it is called the characteristic <\/a>of the field.<\/p>\n<\/div>\n

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 n\u00a0<\/sup>for some integer n<\/p>\n

\n

 <\/p>\n

For every prime number p<\/em> and every positive integer n<\/em>, there are finite fields of order p<\/em>n<\/em><\/sup>, and all fields of this order are isomorphic. <\/a>One may therefore identify all fields of order p<\/em>n<\/em><\/sup>, which are therefore unambiguously denoted , F<\/strong>p<\/em>n<\/em><\/sup> or GF(p<\/em>n<\/em><\/sup>), where the letters GF stand for “Galois field”.<\/p>\n

 <\/p>\n

The identity<\/p>\n

 <\/p>\n

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

 <\/p>\n

 <\/p>\n

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

\n

 <\/p>\n

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

 <\/p>\n

 <\/p>\n

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

 <\/p>\n

The uniqueness up to isomorphism of splitting fields implies thus that all fields of order q<\/em> are isomorphic.<\/p>\n

 <\/p>\n

In summary, we have the following classification theorem first proved in 1893 by E. H. Moore:<\/a><\/p>\n

 <\/p>\n

The order of a finite field is a prime power. For every prime power q there are fields of order q<\/em>, and they are all isomorphic. In these fields, every element satisfies and the polynomial X<\/em>q<\/em> \u2212 X factors as<\/em>:<\/p>\n

 <\/p>\n

It follows that GF(p<\/em>n<\/em>) contains a subfield isomorphic to GF(p<\/em>m<\/em>) if and only if m<\/em> is a divisor of n<\/em>; in that case, this subfield is unique. In fact, the polynomial X<\/em>pm<\/em> \u2212 X<\/em> divides X<\/em>pn<\/em> \u2212 X<\/em> if and only if m<\/em> is a divisor of n<\/em>.<\/p>\n

 <\/p>\n

Non-prime fields<\/strong><\/p>\n

 <\/p>\n

Given a prime power q = pn<\/sup> 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.<\/p>\n

 <\/p>\n

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

 <\/p>\n

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 Xn<\/sup> + aX + b may not exist. In characteristic 2, if the polynomial Xn<\/sup> + X + 1 is reducible, it is recommended to choose Xn<\/sup> + X k<\/sup> + 1 with the lowest possible k that makes the polynomial irreducible. If all these trinomials are reducible, one chooses “pentanomials” X n<\/sup> + X a<\/sup> + X b<\/sup> + X c<\/sup> + 1, as polynomials of degree
\ngreater than 1, with an even number of terms, are never irreducible in characteristic 2, having 1 as a root. “pentanomials” X<\/em>n<\/em><\/sup> + X<\/em>a<\/em><\/sup> + X<\/em>b<\/em><\/sup> + X<\/em>c<\/em><\/sup> + 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.<\/p>\n

 <\/p>\n

 <\/p>\n

 <\/p>\n

Summary<\/strong><\/p>\n

 <\/p>\n

\u00d8 Outlined the algebraic structures<\/p>\n

\u00d8 Discussed about the groups, rings and fields with examples.<\/p>\n

\u00d8 Discussed about the galois field to perform modulo prime p with some examples.<\/p>\n\n\n\n
you can view video on Algebraic Structures and Finite Fields 1<\/strong><\/td>\n\"\"<\/a><\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

\"\"<\/p>\n","protected":false},"author":3,"menu_order":7,"template":"","meta":{"pb_show_title":"on","pb_short_title":"","pb_subtitle":"","pb_authors":["dr-kulothungan"],"pb_section_license":""},"chapter-type":[],"contributor":[58],"license":[],"class_list":["post-84","chapter","type-chapter","status-publish","hentry","contributor-dr-kulothungan"],"part":3,"_links":{"self":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp11\/wp-json\/pressbooks\/v2\/chapters\/84","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp11\/wp-json\/pressbooks\/v2\/chapters"}],"about":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp11\/wp-json\/wp\/v2\/types\/chapter"}],"author":[{"embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp11\/wp-json\/wp\/v2\/users\/3"}],"version-history":[{"count":6,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp11\/wp-json\/pressbooks\/v2\/chapters\/84\/revisions"}],"predecessor-version":[{"id":537,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp11\/wp-json\/pressbooks\/v2\/chapters\/84\/revisions\/537"}],"part":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp11\/wp-json\/pressbooks\/v2\/parts\/3"}],"metadata":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp11\/wp-json\/pressbooks\/v2\/chapters\/84\/metadata\/"}],"wp:attachment":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp11\/wp-json\/wp\/v2\/media?parent=84"}],"wp:term":[{"taxonomy":"chapter-type","embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp11\/wp-json\/pressbooks\/v2\/chapter-type?post=84"},{"taxonomy":"contributor","embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp11\/wp-json\/wp\/v2\/contributor?post=84"},{"taxonomy":"license","embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp11\/wp-json\/wp\/v2\/license?post=84"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}