tailieunhanh - Lecture notes on Computer and network security: Lecture 6 - Avinash Kak

Lecture 6, finite fields (Part 3: Polynomial arithmetic theoretical underpinnings of modern cryptography). The goals of this chapter are: To review polynomial arithmetic, polynomial arithmetic when the coefficients are drawn from a finite field, the concept of an irreducible polynomial, polynomials over the GF(2) finite field. | Lecture 6: Finite Fields (PART 3) PART 3: Polynomial Arithmetic Theoretical Underpinnings of Modern Cryptography Lecture Notes on “Computer and Network Security” by Avi Kak (kak@) February 5, 2016 12:49 Noon c 2016 Avinash Kak, Purdue University Goals: • To review polynomial arithmetic • Polynomial arithmetic when the coefficients are drawn from a finite field • The concept of an irreducible polynomial • Polynomials over the GF (2) finite field CONTENTS Section Title Page Polynomial Arithmetic 3 Arithmetic Operations on Polynomials 5 Dividing One Polynomial by Another Using Long Division 7 Arithmetic Operations on Polynomial Whose Coefficients Belong to a Finite Field 9 Dividing Polynomials Defined over a Finite Field 11 Let’s Now Consider Polynomials Defined over GF (2) 13 Arithmetic Operations on Polynomials over GF (2) 15 So What Sort of Questions Does Polynomial Arithmetic Address? 17 Polynomials over a Finite Field Constitute a Ring 18 When is Polynomial Division Permitted? 20 Irreducible Polynomials, Prime Polynomials 22 Homework Problems 23 2 Computer and Network Security by Avi Kak Lecture 6 : POLYNOMIAL ARITHMETIC • Why study polynomial arithmetic? As you will see in the next lecture, defining finite fields over sets of polynomials will allow us to create a finite set of numbers that are particularly appropriate for digital computation. Since these numbers will constitute a finite field, we will be able to carry out all arithmetic operations on them — in particular the operation of division — without error. • A polynomial is an expression of the form anxn + an−1 xn−1 + + a1x + a0 for some non-negative integer n and where the coefficients a0, a1, , an are drawn from some designated set S. S is called the coefficient set. • When an = 0, we have a polynomial of degree n. • A zeroth-degree polynomial is called a constant polynomial. 3 Computer and Network .