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

Lecture 7, finite fields (Part 4: Finite fields of the form GF(2n ) - Theoretical underpinnings of modern cryptography). The goals of this chapter are: To review finite fields of the form GF(2n), to show how arithmetic operations can be carried out by directly operating on the bit patterns for the elements of GF(2n), Perl and Python implementations for arithmetic in a Galois Field using my BitVector modules. | Lecture 7: Finite Fields (PART 4) PART 4: Finite Fields of the Form GF (2n) Theoretical Underpinnings of Modern Cryptography Lecture Notes on “Computer and Network Security” by Avi Kak (kak@) February 5, 2016 2:04am c 2016 Avinash Kak, Purdue University Goals: • To review finite fields of the form GF (2n) • To show how arithmetic operations can be carried out by directly operating on the bit patterns for the elements of GF (2n) • Perl and Python implementations for arithmetic in a Galois Field using my BitVector modules CONTENTS Section Title Page Consider Again the Polynomials over GF (2) 3 Modular Polynomial Arithmetic 5 How Large is the Set of Polynomials When Multiplications are Carried Out Modulo x2 + x + 1 7 How Do We Know that GF (23 ) is a Finite Field? 9 GF (2n ) a Finite Field for Every n 13 Representing the Individual Polynomials in GF (2n ) by Binary Code Words 14 Some Observations on Bit-Pattern Additions in GF (2n ) 17 Some Observations on Arithmetic Multiplication in GF (2n ) 19 Direct Bitwise Operations for Multiplication in GF (28 ) 21 Summary of How a Multiplication is Carried Out in GF (28 ) 24 Finding Multiplicative Inverses in GF (2n ) with Implementations in Perl and Python 26 Using a Generator to Represent the Elements of GF (2n ) 34 Homework Problems 38 2 Computer and Network Security by Avi Kak Lecture 7 : CONSIDER AGAIN THE POLYNOMIALS OVER GF (2) • Here are some examples: x + 1 x2 + x + 1 x2 + 1 x3 + 1 x 1 x5 x10000 We could also have shown polynomials with negative coefficients, but recall that -1 is the same as +1 in GF (2), • Obviously, the number of such polynomials is infinite. • The polynomials can be subject to the algebraic operations of addition and multiplication in which the coefficients are added and multiplied according to the rules that apply to GF (2). 3 Computer and Network Security by Avi Kak Lecture 7 • As .