Applied Algebra: Codes, Ciphers and Discrete Algorithms

✍ Scribed by Darel W. Hardy, Fred Richman, Carol L. Walker

• Publisher: Chapman and Hall/CRC
• Year: 2009
• Tongue: English
• Leaves: 424
• Series: Discrete Mathematics and Its Applications
• Edition: 2nd
• Category: Library

✦ Synopsis

Using mathematical tools from number theory and finite fields, Applied Algebra: Codes, Ciphers, and Discrete Algorithms, Second Edition presents practical methods for solving problems in data security and data integrity. It is designed for an applied algebra course for students who have had prior classes in abstract or linear algebra. While the content has been reworked and improved, this edition continues to cover many algorithms that arise in cryptography and error-control codes. New to the Second Edition A CD-ROM containing an interactive version of the book that is powered by Scientific Notebook®, a mathematical word processor and easy-to-use computer algebra system New appendix that reviews prerequisite topics in algebra and number theory Double the number of exercises Instead of a general study on finite groups, the book considers finite groups of permutations and develops just enough of the theory of finite fields to facilitate construction of the fields used for error-control codes and the Advanced Encryption Standard. It also deals with integers and polynomials. Explaining the mathematics as needed, this text thoroughly explores how mathematical techniques can be used to solve practical problems. About the AuthorsDarel W. Hardy is Professor Emeritus in the Department of Mathematics at Colorado State University. His research interests include applied algebra and semigroups. Fred Richman is a professor in the Department of Mathematical Sciences at Florida Atlantic University. His research interests include Abelian group theory and constructive mathematics. Carol L. Walker is Associate Dean Emeritus in the Department of Mathematical Sciences at New Mexico State University. Her research interests include Abelian group theory, applications of homological algebra and category theory, and the mathematics of fuzzy sets and fuzzy logic.

✦ Table of Contents

Contents......Page 5
Preface......Page 9
1.1 Integers......Page 13
1.2 Computer Algebra vs. Numerical Analysis......Page 16
1.3 Sums and Products......Page 18
1.4 Mathematical Induction......Page 20
2.1 Binary and Hexadecimal Codes......Page 27
2.2 ASCII Code......Page 34
2.3 Morse Code......Page 36
2.4 Braille......Page 39
2.5 Two-out-of-Five Code......Page 44
2.6 Hollerith Codes......Page 46
3.1 The Mod Function......Page 51
3.2 Greatest Common Divisors......Page 54
3.3 Extended Euclidean Algorithm......Page 59
3.4 The Fundamental Theorem of Arithmetic......Page 64
3.5 Modular Arithmetic......Page 67
4.1 Cryptography......Page 73
4.2 Crypt analysis......Page 80
4.3 Substitution and Permutation Ciphers......Page 87
4.4 Block Ciphers......Page 94
4.5 The Playfair Cipher......Page 100
4.6 Unbreakable Ciphers......Page 104
4.7 Enigma Machine......Page 107
5.1 Weights and Hamming Distance......Page 113
5.2 Bar Codes Based on Two-out-of-Five Code......Page 118
5.3 Other Commercial Codes......Page 124
5.4 Hamming (7, 4) Code......Page 132
6.1 Systems of Linear Equations Modulo n......Page 139
6.2 Chinese Remainder Theorem......Page 144
6.3 Extended Precision Arithmetic......Page 149
6.4 Greatest Common Divisor of Polynomials......Page 153
6.5 Hilbert Matrix......Page 159
7.1 Wilson's Theorem......Page 165
7.2 Powers Modulo n......Page 167
7.3 Fermat's Little Theorem......Page 170
7.4 Rabin's Probabilistic Primality Test......Page 175
7.5 Exponential Ciphers......Page 180
7.6 Euler's Theorem......Page 183
8.1 The Rivest-Shamir-Adleman Cipher System......Page 189
8.2 Electronic Signatures......Page 195
8.3 A System for Exchanging Messages......Page 197
8.4 Knapsack Ciphers......Page 202
8.5 Digital Signature Standard......Page 206
9.1 The Galois Field GF_V......Page 211
9.2 The Ring GF_p[x] of Polynomials......Page 216
9.3 The Galois Field GF_4......Page 224
9.4 The Galois Fields GF_8 and GF_{16}......Page 229
9.5 The Galois Field GF_{p^n}......Page 237
9.6 The Multiplicative Group of GF_{p^n}......Page 241
9.7 Random Number Generators......Page 247
10 Error-Correcting Codes......Page 253
10.1 BCH Codes......Page 254
10.2 A BCH Decoder......Page 261
10.3 Reed-Solomon Codes......Page 270
11 Advanced Encryption Standard......Page 273
11.1 Data Encryption Standard......Page 274
11.2 The Galois Field GF256......Page 277
11.3 The Rijndael Block Cipher......Page 282
12.1 Lagrange Interpolation Formula......Page 289
12.2 Kronecker's Algorithm......Page 294
12.3 Neville's Iterated Interpolation Algorithm......Page 297
12.4 Secure Multiparty Protocols......Page 302
12.5 Discrete Fourier Transforms......Page 304
12.6 Fast Fourier Interpolation......Page 313
A.l Number Theory......Page 319
A.2 Groups......Page 320
A.3 Rings and Polynomials......Page 322
A.4 Fields......Page 323
A.5 Linear Algebra and Matrices......Page 324
Solutions to Odd Problems......Page 329
Bibliography......Page 407
Notation......Page 409
Algorithms......Page 411
Figures......Page 413
Tables......Page 415
Index......Page 417