Research project paper.
anve5h.5p10
Chapter5.pptxCryptography and Network Security: Principles and Practice
Eighth Edition
Chapter 5
Finite Fields
Copyright © 2020 Pearson Education, Inc. All Rights Reserved.
Copyright © 2020 Pearson Education, Inc. All Rights Reserved.
Lecture slides prepared for “Cryptography and Network Security”, 8/e, by William Stallings, Chapter 5 – “Finite Fields”.
Finite fields have become increasingly important in cryptography. A number of
cryptographic algorithms rely heavily on properties of finite fields, notably the
Advanced Encryption Standard (AES) and elliptic curve cryptography. Other examples
include the message authentication code CMAC and the authenticated encryption
scheme GCM.
This chapter provides the reader with sufficient background on the concepts of
finite fields to be able to understand the design of AES and other cryptographic algorithms
that use finite fields. Because students unfamiliar with abstract algebra may find
the concepts behind finite fields somewhat difficult to grasp, we approach the topic in a
way designed to enhance understanding. Our plan of attack is as follows:
1. Fields are a subset of a larger class of algebraic structures called rings, which
are in turn a subset of the larger class of groups. In fact, as shown in Figure 5.1,
both groups and rings can be further differentiated. Groups are defined by
a simple set of properties and are easily understood. Each successive subset
(abelian group, ring, commutative ring, and so on) adds additional properties
and is thus more complex. Sections 5.1 through 5.3 will examine groups, rings,
and fields, successively.
2. Finite fields are a subset of fields, consisting of those fields with a finite number
of elements. These are the class of fields that are found in cryptographic
algorithms. With the concepts of fields in hand, we turn in Section 5.4 to a
specific class of finite fields, namely those with p elements, where p is prime.
Certain asymmetric cryptographic algorithms make use of such fields.
3. A more important class of finite fields, for cryptography, comprises those with
2n elements depicted as fields of the form GF(2n ). These are used in a wide
variety of cryptographic algorithms. However, before discussing these fields, we
need to analyze the topic of polynomial arithmetic, which is done in Section 5.5.
4. With all of this preliminary work done, we are able at last, in Section 5.6, to
discuss finite fields of the form GF(2n ).
Before proceeding, the reader may wish to review Sections 2.1 through 2.3, which
cover relevant topics in number theory.
1
Learning Objectives
Distinguish among groups, rings, and fields.
Define finite fields of the form GF(p)
Explain the differences among ordinary polynomial arithmetic, polynomial arithmetic with coefficients in Zp, and modular polynomial arithmetic in GF(2n).
Define finite fields of the form GF(2n).
Explain the two different uses of the mod operator.
Copyright © 2020 Pearson Education, Inc. All Rights Reserved.
Figure 5.1 Groups, Rings, and Fields
Copyright © 2020 Pearson Education, Inc. All Rights Reserved.
Groups, rings, and fields are the fundamental elements of a branch of mathematics
known as abstract algebra, or modern algebra. In abstract algebra, we are concerned
with sets on whose elements we can operate algebraically; that is, we can combine
two elements of the set, perhaps in several ways, to obtain a third element of the set.
These operations are subject to specific rules, which define the nature of the set. By
convention, the notation for the two principal classes of operations on set elements is
usually the same as the notation for addition and multiplication on ordinary numbers.
However, it is important to note that, in abstract algebra, we are not limited to
ordinary arithmetical operations. All this should become clear as we proceed.
3
Groups
A set of elements with a binary operation denoted by • that associates to each ordered pair (a,b) of elements in G an element (a • b ) in G, such that the following axioms are obeyed:
(A1) Closure:
If a and b belong to G, then a • b is also in G
(A2) Associative:
a • (b • c) = (a • b) • c for all a, b, c in G
(A3) Identity element:
There is an element e in G such that a • e = e • a = a for all a in G
(A4) Inverse element:
For each a in G, there is an element a1 in G such that a • a1 = a1 • a = e
(A5) Commutative:
a • b = b • a for all a, b in G
Copyright © 2020 Pearson Education, Inc. All Rights Reserved.
A group G , sometimes denoted by {G , * }, is a set of elements with a binary operation
denoted by * that associates to each ordered pair (a, b ) of elements in G an element
(a * b ) in G , such that the following axioms are obeyed:
(A1) Closure:
If a and b belong to G, then a * b is also in G
(A2) Associative:
a * (b * c) = (a * b) * c for all a, b, c in G
(A3) Identity element:
There is an element e in G such that a * e = e * a = a for all a in G
(A4) Inverse element:
For each a in G, there is an element a1 in G such that a*a1 = a1 * a = e
(A5) Commutative:
a * b = b * a for all a, b in G
If a group has a finite number of elements, it is referred to as a finite group , and
the order of the group is equal to the number of elements in the group. Otherwise,
the group is an infinite group .
A group is said to be abelian if it satisfies the following additional condition:
(A5) Commutative: a * b = b * a for all a, b in G.
4
Cyclic Group
Exponentiation is defined within a group as a repeated application of the group operator, so that a3 = a • a • a
We define a0 = e as the identity element, and a−n = (a’)n, where a’ is the inverse element of a within the group
A group G is cyclic if every element of G is a power ak (k is an integer) of a fixed element a € G
The element a is said to generate the group G or to be a generator of G
A cyclic group is always abelian and may be finite or infinite
Copyright © 2020 Pearson Education, Inc. All Rights Reserved.
We define exponentiation within a group as a repeated application of the group operator, so that a3 = a *a * a. Furthermore, we define a0 = e as the identity element, and a-n = (a′)n, where a′ is the inverse element of a within the group. A group G is cyclic if every element of G is a power ak (k is an integer) of a fixed element a ∈ G. The element a is said to generate the group G or to be a generator of G. A cyclic group is always abelian and may be finite or infinite.
5
Rings (1 of 3)
A ring R , sometimes denoted by {R , + , * }, is a set of elements with two binary operations, called addition and multiplication, such that for all a , b , c in R the following axioms are obeyed:
(A1–A5)
R is an abelian group with respect to addition; that is, R satisfies axioms A1 through A5. For the case of an additive group, we denote the identity element as 0 and the inverse of a as –a
(M1) Closure under multiplication:
If a and b belong to R , then ab is also in R
(M2) Associativity of multiplication:
a (bc ) = (ab)c for all a , b , c in R
Copyright © 2020 Pearson Education, Inc. All Rights Reserved.
A ring R , sometimes denoted by {R , + , * }, is a set of elements with two binary operations, called addition and multiplication, such that for all a , b , c in R the following axioms are obeyed:
(A1–A5)
R is an abelian group with respect to addition; that is, R satisfies axioms A1 through A5. For the case of an additive group, we denote the identity element as 0 and the inverse of a as –a
(M1) Closure under multiplication:
If a and b belong to R , then ab is also in R
(M2) Associativity of multiplication:
a (bc ) = (ab)c for all a , b , c in R
(M3) Distributive laws:
a (b + c ) = ab + ac for all a , b , c in R
(a + b )c = ac + bc for all a , b , c in R
In essence, a ring is a set in which we can do addition, subtraction [a - b = a + (-b )], and multiplication without leaving the set.
6
Rings (2 of 3)
(M3) Distributive laws:
a (b + c ) = ab + ac for all a, b, c in R
(a + b )c = ac + bc for all a, b, c in R
In essence, a ring is a set in which we can do addition, subtraction [a − b = a + (−b )], and multiplication without leaving the set
Copyright © 2020 Pearson Education, Inc. All Rights Reserved.
A ring R , sometimes denoted by {R , + , * }, is a set of elements with two binary operations, called addition and multiplication, such that for all a , b , c in R the following axioms are obeyed:
(A1–A5)
R is an abelian group with respect to addition; that is, R satisfies axioms A1 through A5. For the case of an additive group, we denote the identity element as 0 and the inverse of a as –a
(M1) Closure under multiplication:
If a and b belong to R , then ab is also in R
(M2) Associativity of multiplication:
a (bc ) = (ab)c for all a , b , c in R
(M3) Distributive laws:
a (b + c ) = ab + ac for all a , b , c in R
(a + b )c = ac + bc for all a , b , c in R
In essence, a ring is a set in which we can do addition, subtraction [a - b = a + (-b )], and multiplication without leaving the set.
7
Rings (3 of 3)
A ring is said to be commutative if it satisfies the following additional condition:
(M4) Commutativity of multiplication:
ab = ba for all a, b in R
An integral domain is a commutative ring that obeys the following axioms.
(M5) Multiplicative identity:
There is an element 1 in R such that a1 = 1a = a for all a in R
(M6) No zero divisors:
If a , b in R and ab = 0, then either a = 0 or b = 0
Copyright © 2020 Pearson Education, Inc. All Rights Reserved.
A ring is said to be commutative if it satisfies the following additional condition:
(M4) Commutativity of multiplication:
ab = ba for all a, b in R
An integral domain is a commutative ring that obeys the following axioms.
(M5) Multiplicative identity:
There is an element 1 in R such that a 1 = 1a = a for all a in R
(M6) No zero divisors:
If a , b in R and ab = 0, then either a = 0 or b = 0
8
Fields
A field F , sometimes denoted by {F, +,* }, is a set of elements with two binary operations, called addition and multiplication, such that for all a, b, c in F the following axioms are obeyed:
(A1–M6)
F is an integral domain; that is, F satisfies axioms A1 through A5 and M1 through M6
(M7) Multiplicative inverse:
For each a in F, except 0, there is an element a−1 in F such that aa−1 = (a−1 )a = 1
In essence, a field is a set in which we can do addition, subtraction, multiplication, and division without leaving the set. Division is defined with the following rule: a /b = a (b−1 )
Familiar examples of fields are the rational numbers, the real numbers, and the complex numbers. Note that the set of all integers is not a field, because not every element of the set has a multiplicative inverse.
Copyright © 2020 Pearson Education, Inc. All Rights Reserved.
A field F, sometimes denoted by {F , + , * }, is a set of elements with two binary operations,
called addition and multiplication, such that for all a, b, c in F the following
axioms are obeyed.
(A1–M6) F is an integral domain; that is, F satisfies axioms A1 through A5 and
M1 through M6.
(M7) Multiplicative inverse: For each a in F , except 0, there is an element
a-1 in F such that aa-1 = (a-1 )a = 1.
In essence, a field is a set in which we can do addition, subtraction, multiplication,
and division without leaving the set. Division is defined with the following rule: a /b = a (b-1 ).
Familiar examples of fields are the rational numbers, the real numbers, and the complex numbers. Note that the set of all integers is not a field, because not every element of the set has a multiplicative inverse; in fact, only the elements 1 and - 1 have multiplicative inverses in the integers.
9
Figure 5.2 Properties of Groups, Rings, and Fields
Copyright © 2020 Pearson Education, Inc. All Rights Reserved.
Figure 5.2 summarizes the axioms that define groups, rings, and fields.
10
Figure 5.3 Types of Fields
Copyright © 2020 Pearson Education, Inc. All Rights Reserved.
In Section 5.3, we defined a field as a set that obeys all of the axioms of Figure 5.2
and gave some examples of infinite fields. Infinite fields are not of particular interest
in the context of cryptography. However, in addition to infinite fields, there are
two types of finite fields, as illustrated in Figure 5.3. Finite fields play a crucial role
in many cryptographic algorithms.
11
Finite Fields of the Form GF(p)
Finite fields play a crucial role in many cryptographic algorithms
It can be shown that the order of a finite field must be a power of a prime pn, where n is a positive integer
The finite field of order pn is generally written GF(pn)
GF stands for Galois field, in honor of the mathematician who first studied finite fields
Copyright © 2020 Pearson Education, Inc. All Rights Reserved.
It can be shown that the order of a finite field (number of
elements in the field) must be a power of a prime pn , where n is a positive integer.
The finite field of order pn is generally written GF(pn); GF stands for Galois
field, in honor of the mathematician who first studied finite fields. Two special cases
are of interest for our purposes. For n = 1, we have the finite field GF(p); this finite
field has a different structure than that for finite fields with n > 1 and is studied in
this section.
12
Table 5.1 Arithmetic Modulo 8 and Modulo 7(1 of 6)
(a) Addition modulo 8
Copyright © 2020 Pearson Education, Inc. All Rights Reserved.
Table 5.1 Arithmetic Modulo 8 and Modulo 7
13
Table 5.1 Arithmetic Modulo 8 and Modulo 7 (2 of 6)
(b) Multiplication modulo 8
Copyright © 2020 Pearson Education, Inc. All Rights Reserved.
Table 5.1 Arithmetic Modulo 8 and Modulo 7
14
Table 5.1 Arithmetic Modulo 8 and Modulo 7 (3 of 6)
(c) Additive and multiplicative inverses modulo 8
Copyright © 2020 Pearson Education, Inc. All Rights Reserved.
Table 5.1 Arithmetic Modulo 8 and Modulo 7
15
Table 5.1 Arithmetic Modulo 8 and Modulo 7 (4 of 6)
(d) Addition modulo 7
Copyright © 2020 Pearson Education, Inc. All Rights Reserved.
Table 5.1 Arithmetic Modulo 8 and Modulo 7
16
Table 5.1 Arithmetic Modulo 8 and Modulo 7 (5 of 6)
(e) Multiplication modulo 7
Copyright © 2020 Pearson Education, Inc. All Rights Reserved.
Table 5.1 Arithmetic Modulo 8 and Modulo 7
17
Table 5.1 Arithmetic Modulo 8 and Modulo 7 (6 of 6)
(f) Additive and multiplicative inverses modulo 7
Copyright © 2020 Pearson Education, Inc. All Rights Reserved.
Table 5.1 Arithmetic Modulo 8 and Modulo 7
18
In this section, we have shown how to construct a finite field of order p, where p is prime
GF(p) is defined with the following properties:
1. GF(p) consists of p elements
2. The binary operations + and * are defined over the set. The operations of addition, subtraction, multiplication, and division can be performed without leaving the set. Each element of the set other than 0 has a multiplicative inverse
We have shown that the elements of GF(p) are the integers {0, 1, . . . , p – 1} and that the arithmetic operations are addition and multiplication mod p
Copyright © 2020 Pearson Education, Inc. All Rights Reserved.
In this section, we have shown how to construct a finite field of order p, where p is prime. GF(p) is defined with the following properties:
GF(p) consists of p elements
2. The binary operations + and * are defined over the set. The operations of addition, subtraction, multiplication, and division can be performed without leaving the set. Each element of the set other than 0 has a multiplicative inverse
We have shown that the elements of GF(p) are the integers {0, 1, . . . , p – 1} and that the arithmetic operations are addition and multiplication mod p
19
Figure 5.4 Treatment of Polynomials
Copyright © 2020 Pearson Education, Inc. All Rights Reserved.
Before continuing our discussion of finite fields, we need to introduce the interesting
subject of polynomial arithmetic. We are concerned with polynomials in a single
variable x , and we can distinguish three classes of polynomial arithmetic. (Figure 5.4)
• Ordinary polynomial arithmetic, using the basic rules of algebra.
• Polynomial arithmetic in which the arithmetic on the coefficients is performed
modulo p ; that is, the coefficients are in GF(p ).
• Polynomial arithmetic in which the coefficients are in GF(p ), and the polynomials
are defined modulo a polynomial m (x ) whose highest power is some integer n .
20
Figure 5.5 Examples of Polynomial Arithmetic
Copyright © 2020 Pearson Education, Inc. All Rights Reserved.
Examples of Polynomial Arithmetic
21
Polynomial Arithmetic With Coefficients in Zp
If each distinct polynomial is considered to be an element of the set, then that set is a ring
When polynomial arithmetic is performed on polynomials over a field, then division is possible
Note: this does not mean that exact division is possible
If we attempt to perform polynomial division over a coefficient set that is not a field, we find that division is not always defined
Even if the coefficient set is a field, polynomial division is not necessarily exact
With the understanding that remainders are allowed, we can say that polynomial division is possible if the coefficient set is a field
Copyright © 2020 Pearson Education, Inc. All Rights Reserved.
Let us now consider polynomials in which the coefficients are elements of some
field F; we refer to this as a polynomial over the field F. In that case, it is easy to
show that the set of such polynomials is a ring, referred to as a polynomial ring .
That is, if we consider each distinct polynomial to be an element of the set, then
that set is a ring.
When polynomial arithmetic is performed on polynomials over a field, then
division is possible. Note that this does not mean that exact division is possible.
Let us clarify this distinction. Within a field, given two elements a and b , the
quotient a /b is also an element of the field. However, given a ring R that is not a
field, in general, division will result in both a quotient and a remainder; this is not
exact division.
Now, if we attempt to perform polynomial division over a coefficient set that
is not a field, we find that division is not always defined.
However, as we demonstrate presently, even if the coefficient set is a field,
polynomial division is not necessarily exact. In general, division will produce a quotient
and a remainder.
With the understanding that remainders are allowed, we can say that polynomial
division is possible if the coefficient set is a field.
22
Polynomial Division
We can write any polynomial in the form:
f(x) = q(x) g(x) + r(x)
r(x) can be interpreted as being a remainder
So r(x) = f(x) mod g(x)
If there is no remainder we can say g(x) divides f(x)
Written as g(x) | f(x)
We can say that g(x) is a factor of f(x)
Or g(x) is a divisor of f(x)
A polynomial f(x) over a field F is called irreducible if and only if f(x) cannot be expressed as a product of two polynomials, both over F, and both of degree lower than that of f(x)
An irreducible polynomial is also called a prime polynomial
Copyright © 2020 Pearson Education, Inc. All Rights Reserved.
Note that we can write any polynomial in the form of f(x) = q(x) g(x) + r(x), where division of f(x) by g(x) results in a quotient q(x) and remainder r(x). Can then extend the concept of divisors from the integer case, and show that the Euclidean algorithm can be extended to find the greatest common divisor of two polynomials whose coefficients are elements of a field.
Define an irreducible (or prime) polynomial as one with no divisors other than itself & 1. If compute polynomial arithmetic modulo an irreducible polynomial, this forms a finite field, and the GCD & Inverse algorithms can be adapted for it.
23
Example of Polynomial Arithmetic Over GF(2) (1 of 2)
(a) Addition
(b) Subtraction
Copyright © 2020 Pearson Education, Inc. All Rights Reserved.
Figure 5.6 shows an example of polynomial arithmetic over GF(2).
24
Example of Polynomial Arithmetic Over GF(2) (2 of 2)
(c) Multiplication
(d) Division
Copyright © 2020 Pearson Education, Inc. All Rights Reserved.
Figure 5.6 shows an example of polynomial arithmetic over GF(2).
25
Polynomial G C D
The polynomial c(x) is said to be the greatest common divisor of a(x) and b(x) if the following are true:
c(x) divides both a(x) and b(x)
Any divisor of a(x) and b(x) is a divisor of c(x)
An equivalent definition is:
gcd[a(x), b(x)] is the polynomial of maximum degree that divides both a(x) and b(x)
The Euclidean algorithm can be extended to find the greatest common divisor of two polynomials whose coefficients are elements of a field
Copyright © 2020 Pearson Education, Inc. All Rights Reserved.
We can extend the analogy between polynomial arithmetic over a field and integer
arithmetic by defining the greatest common divisor as follows. The polynomial c(x)
is said to be the greatest common divisor of a(x) and b(x) if the following are true.
1. c(x) divides both a(x) and b(x).
2. Any divisor of a(x) and b(x) is a divisor of c(x).
An equivalent definition is the following: gcd[a (x ), b (x )] is the polynomial of
maximum degree that divides both a (x ) and b (x ).
We can adapt the Euclidean algorithm to compute the greatest common
Divisor of two polynomials.
26
Table 5.2 Arithmetic in GF(23) (1 of 3)
(a) Addition
Copyright © 2020 Pearson Education, Inc. All Rights Reserved.
Table 5.2 Arithmetic in GF(23)
27
Table 5.2 Arithmetic in GF(23) (2 of 3)
(b) Multiplication
Copyright © 2020 Pearson Education, Inc. All Rights Reserved.
Table 5.2 Arithmetic in GF(23)
28
Table 5.2 Arithmetic in GF(23) (3 of 3)
(c) Additive and multiplicative inverses
Copyright © 2020 Pearson Education, Inc. All Rights Reserved.
Table 5.2 Arithmetic in GF(23)
29
Table 5.3 Polynomial Arithmetic Modulo (x3 + x + 1) (1 of 2)
(a) Addition
Copyright © 2020 Pearson Education, Inc. All Rights Reserved.
Example shows addition & multiplication in GF(23)
30
Table 5.3 Polynomial Arithmetic Modulo (x3 + x + 1) (2 of 2)
(b) Multiplication
Copyright © 2020 Pearson Education, Inc. All Rights Reserved.
Example shows addition & multiplication in GF(23)
31
Table 5.4 Extended Euclid [(x8 + x4 + x3 + x + 1), (x7 + x + 1)]
(Table 5.4 can be found on page 138 in textbook)
| Initialization | a(x) = x8 + x4 + x3 + x + 1; v-1(x) = 1; w-1(x) = 0 b(x) = x7 + x + 1; v0(x) = 0; w0(x) = 1 |
| Iteration 1 | q1(x) = x; r1 (x) = x4 + x3 + x2 + 1 v1(x) = 1; w1(x) = x |
| Iteration 2 | q2(x) = x3 + x2 + 1; r2(x) = x v2(x) = x3 + x2 + 1; w2(x) = x4 + x3 + x + 1 |
| Iteration 3 | q3(x) = x3 + x2 + x; r3(x) = 1 v3(x) = x6 + x2 + x + 1; w3(x) = x7 |
| Iteration 4 | q4(x) = x; r4(x) = 0 v4(x) = x7 + x + 1; w4(x) = x8 + x4 + x3 + x + 1 |
| Result | d(x) = r3(x) = gcd(a(x), b(x)) = 1 w(x) = w3(x) = (x7 + x + 1)-1 mod (x8 + x4 + x3 + x + 1) = x7 |
Copyright © 2020 Pearson Education, Inc. All Rights Reserved.
Table 5.4 Extended Euclid [(x8 + x4 + x3 + x + 1), (x7 + x + 1)]
32
Computational Considerations
Since coefficients are 0 or 1, they can represent any such polynomial as a bit string
Addition becomes XOR of these bit strings
Multiplication is shift and XOR
cf long-hand multiplication
Modulo reduction is done by repeatedly substituting highest power with remainder of irreducible polynomial (also shift and XOR)
Copyright © 2020 Pearson Education, Inc. All Rights Reserved.
A key motivation for using polynomial arithmetic in GF(2n) is that the polynomials can be represented as a bit string, using all possible bit values, and the calculations only use simple common machine instructions - addition is just XOR, and multiplication is shifts & XOR’s. See text for additional discussion. The shortcut for polynomial reduction comes from the observation that if in GF(2n) then irreducible poly g(x) has highest term xn , and if compute xn mod g(x) answer is g(x)- xn
33
Using a Generator
A generator g of a finite field F of order q (contains q elements) is an element whose first q−1 powers generate all the nonzero elements of F
The elements of F consist of 0, g0, g1, . . . ., gq−2
Consider a field F defined by a polynomial fx
An element b contained in F is called a root of the polynomial if f(b) = 0
Finally, it can be shown that a root g of an irreducible polynomial is a generator of the finite field defined on that polynomial
Copyright © 2020 Pearson Education, Inc. All Rights Reserved.
An equivalent technique for defining a finite field of the form GF(2n ), using the
same irreducible polynomial, is sometimes more convenient. To begin, we need two
definitions: A generator g of a finite field F of order q (contains q elements) is an
element whose first q - 1 powers generate all the nonzero elements of F. That is, the
elements of F consist of 0, g0 , g1 , c , gq-2 .
Consider a field F defined by a polynomial
f (x ). An element b contained in F is called a root of the polynomial if f (b ) = 0.
Finally, it can be shown that a root g of an irreducible polynomial is a generator of the
finite field defined on that polynomial.
34
Table 5.5 Generator for GF(23) using x3 + x + 1
| Power Representation | Polynomial Representation | Binary Representation | Decimal (Hex) Representation |
| 0 | 0 | 000 | 0 |
| g0(= g7) | 1 | 001 | 1 |
| g1 | g | 010 | 2 |
| g2 | g2 | 100 | 4 |
| g3 | g + 1 | 011 | 3 |
| g4 | g2 + g | 110 | 6 |
| g5 | g2 + g + 1 | 111 | 7 |
| g6 | g2 + 1 | 101 | 5 |
Copyright © 2020 Pearson Education, Inc. All Rights Reserved.
Table 5.5 Generator for GF(23) using x3 + x + 1
35
Table 5.6 GF(23) Arithmetic Using Generator for the Polynomial (x3 + x + 1) (1 of 2)
(a) Addition
Copyright © 2020 Pearson Education, Inc. All Rights Reserved.
Table 5.6 GF(23) Arithmetic Using Generator for the Polynomial (x3 + x + 1)
36
Table 5.6 GF(23) Arithmetic Using Generator for the Polynomial (x3 + x + 1) (2 of 2)
(b) Multiplication
Copyright © 2020 Pearson Education, Inc. All Rights Reserved.
Table 5.6 GF(23) Arithmetic Using Generator for the Polynomial (x3 + x + 1)
37
Summary
Distinguish among groups, rings, and fields
Define finite fields of the form GF(p)
Define finite fields of the form GF(2n)
Explain the differences among ordinary polynomial arithmetic, polynomial arithmetic with coefficients in Zp, and modular polynomial arithmetic in GF(2n)
Explain the two different uses of the mod operator
Copyright © 2020 Pearson Education, Inc. All Rights Reserved.
Chapter 5 summary.
38
Copyright
This work is protected by United States copyright laws and is provided solely for the use of instructors in teaching their courses and assessing student learning. Dissemination or sale of any part of this work (including on the World Wide Web) will destroy the integrity of the work and is not permitted. The work and materials from it should never be made available to students except by instructors using the accompanying text in their classes. All recipients of this work are expected to abide by these restrictions and to honor the intended pedagogical purposes and the needs of other instructors who rely on these materials.
Copyright © 2020 Pearson Education, Inc. All Rights Reserved.
39
.MsftOfcThm_Text1_Fill { fill:#000000; } .MsftOfcThm_MainDark1_Stroke { stroke:#000000; }
