## Table of contents for Applied algebra : codes, ciphers, and discrete algorithms / Darel W. Hardy, Fred Richman, Carol L. Walker.

Bibliographic record and links to related information available from the Library of Congress catalog
Note: Electronic data is machine generated. May be incomplete or contain other coding.

```1 Integers and Computer Algebra                             1
1.1 Integers      ................ ...............       1
1.2 Computer Algebra vs. Numerical Analysis . ............  4
1.3  Sums and  Products ...................   .......    6
1.4  Mathematical Induction  ...................     ....  8
2 Codes                                                    15
2.1 Binary and Hexadecimal Codes . .................. 15
2.2 ASCII Code ........... ...........                   22
2.3 Morse Code ...................         ......... . 24
2.4 Braille ............    ........ .......... ..       27
2.5  Two-out-of-Five Code  . .......................     32
2.6  Hollerith Codes  ...................     ........   34
3 Euclidean Algorithm                                      39
3.1  The Mod Function  . .........................       39
3.2  Greatest Common Divisors  ................... ..    42
3.3 Extended Euclidean Algorithm . .................. 47
3.4 The Fundamental Theorem of Arithmetic . ............ 52
3.5 Modular Arithmetic ......................... 55
4 Ciphers                                                  61
4.1 Cryptography ...................        ........ . 61
4.2 Cryptanalysis ...................       ........ . 68
4.3 Substitution and Permutation Ciphers . .............. 75
4.4  Block Ciphers . . . : ...................      .....  82
4.5  The Playfair Cipher  . ........................     88
4.6  Unbreakable Ciphers  ...................     ......  92
4.7  Enigma Machine  ...........................         95
5 Error-Control Codes                                     101
5.1 Weights and Hamming Distance . ................. 101
5.2 Bar Codes Based on Two-out-of-Five Code . ........... 106
5.3 Other Commercial Codes ...... . . . . .  .  .  .  .  .  .   .  112
5.4 Hamming (7, 4) Code ......... . . ... .......... 120
6 Chinese Remainder Theorem                                 127
6.1 Systems of Linear Equations Modulo n . .............. 127
6.2 Chinese Remainder Theorem  .................... 132
6.3 Extended Precision Arithmetic .................... 137
6.4 Greatest Common Divisor of Polynomials . ............ 141
6.5  Hilbert Matrix  ...................       ... . . .  .  147
7 Theorems of Fermat and Euler                             153
7.1  Wilson's Theorem  ................     .   .  .  .  .  .   .  153
7.2  Powers Modulo n  ...................        .. .  .   . .  155
7.3  Fermat's Little Theorem  . .................. .. . . 158
7.4 Rabin's Probabilistic Primality Test . ............... 163
7.5  Exponential Ciphers  ....................          . . . . . .  168
7.6  Euler's Theorem  ....................    .   .  .  .  .  .   171
8 Public Key Ciphers                                        177
8.1 The Rivest-Shamir-Adleman Cipher System . ........... 177
8.2  Electronic Signatures ............... ..  . ........   . . 183
8.3 A System for Exchanging Messages . ................ 185
8.4 Knapsack Ciphers . . ......................... 190
8.5  Digital Signature Standard  ................... .. 194
9 Finite Fields                                            199
9.1  The Galois Field  GFp  . .......................    199
9.2 The Ring GFp[z] of Polynomials .. . . . . .  .  .  .  .  .   . 204
9.3 The Galois Field GF4 .  ....................... 212
9.4 The Galois Fields GFs and GF16 . ................. 217
9.5 The Galois Field GFpn ...... ........... .    .  .  .  .   . 225
9.6 The Multiplicative Group of GFp .. . . . . . .  .  .  .  . . .. . 229
9.7 Random Number Generators ................... . 235
10 Error-Correcting Codes                                  241
10.1 BCH Codes ................... ........... 242
10.2 A BCH Decoder ................... ........ 249
10.3 Reed-Solomon Codes ................... ...... 258
11.1 Data Encryption Standard ................... ... 262
11.2 The Galois Field GF256 .  ...................... 265
11.3 The Rijndael Block Cipher .....     ................ 270
12 Polynomial Algorithms and Fast Fourier Transforms    277
12.1 Lagrange Interpolation Formula . ................ ..277
12.2 Kronecker's Algorithm ... ..................... ....282
12.3  Neville's Iterated Interpolation Algorithm  . . . . . . . . . . .  .  285
12.4  Secure Multiparty Protocols . ................... .  290
12.5 Discrete Fourier Transforms . .................... 292
12.6 Fast Fourier Interpolation . ....................... ...301
Appendix A Topics in Algebra and Number Theory          307
A.1 Number Theory ... . . . . ......................... 307
A.2  Groups . . .... ............................    308
A.3 Rings and Polynomials . ......................  . 310
A.4 Fields ... . . . . ................................ 311
A.5 Linear Algebra and Matrices .  . . . . . .  . . . . .  . 312
Solutions to Odd Problems                               317
Bibliography                                            395
Notation                                                397
Algorithms                                              399

```

Library of Congress subject headings for this publication: Coding theory, Computer security Mathematics