Mathematics for the Digital Systems Engineer

Chris J. Mitchell received his PhD in Mathematics from Westfield College, University of London in 1979. He spent over 10 years in industrial research and development, then took up a chair in Computer Science at Royal Holloway in 1990, where he still works today, specializing in cryptography and information security.

• List of Figures xiList of Tables xiiAbout the Author xiiiPreface: Why This Book? xvAcknowledgements xixTable of Abbreviations xxiAbout the Companion Site xxiii1 A Gentle Introduction 11.1 What Is This Book About? 11.2 Mathematics as Mathematicians See It 21.3 Theorems and Proofs 51.4 Abstract Algebra 81.5 What Do You Need to Know to Make Sense of This Book? 91.6 Case Studies of Applications 92 Sets, Functions and Relations 112.1 Why Are Sets Important? 112.2 Sets 122.3 Cartesian Products of Sets 172.4 Relations 172.5 Equivalence Relations and Equivalence Classes 182.6 Relations: A Detailed Example 212.7 Functions 242.8 Operations 263 Numbers as We Know and Love Them 293.1 Where Does Mathematics Start? 293.2 The Natural Numbers and the Integers 303.3 Writing Down Numbers 323.4 Ordering the Integers 333.5 Induction 353.6 The Division Theorem 383.7 Prime Numbers and Common Factors 403.8 Unique Factorisation 433.9 The Euclidean Algorithm 443.10 The Rationals 463.11 The Real and Complex Numbers 493.12 Applying Complex Numbers—An Everyday Example 504 Modular Arithmetic on the Integers 534.1 Working Relative to a Modulus 534.2 Congruences: Making It More Mathematical 544.3 Parity Checks: Using Modulo 2 Arithmetic 574.4 Check Digits: A More Complex Example 584.5 Elementary Properties of ℤn 614.6 The Extended Euclidean Algorithm 644.7 Cryptography Ancient and Modern 664.8 RSA: How Does It Work? 694.9 Using RSA 724.10 Implementing RSA 754.11 RSA and the Future 784.12 Other Applications of Modular Arithmetic 795 Groups 815.1 What Is a Group? 815.2 A First Example: The Integers 835.3 A Second Example: Modular Addition 845.4 But What About Modular Multiplication? 865.5 Subgroups and Lagrange's Theorem 895.6 Proving Euler's Theorem 925.7 Examples of Non-abelian Groups 955.8 When Are Two Groups the Same Group? 1005.9 Combining Groups 1045.10 Discrete Logarithms 1065.11 Diffie–Hellman Key Agreement 1085.12 Other Applications of Discrete Logarithms 1125.13 The Threat Posed by Quantum Computing 1125.14 Other Applications of Groups 1146 Rings and Fields 1176.1 Two Operations, Not Just One! 1176.2 So What Is a Ring? 1186.3 Types of Rings 1206.4 Combining Rings 1226.5 Integral Domains—Some Key Properties 1246.6 Unique Factorisation Domains—Key Properties 1276.7 When Are Two Rings the Same Ring? 1276.8 Fields 1306.9 Coding Theory 1357 Polynomials and Polynomial Rings 1457.1 What Do I Mean by Polynomials? 1457.2 Doing Arithmetic with Polynomials 1497.3 Polynomials over a Field 1517.4 Shift Register Sequences 1547.5 Polynomial Arithmetic Modulo a Polynomial 1688 Finite Fields 1758.1 The Core of the Book 1758.2 The Prime Fields 1768.3 How Many Elements Might There Be? 1768.4 Prime Power Fields 1778.5 Uniqueness and Representation of Finite Fields 1808.6 Elliptic Curve Cryptography 1818.7 Quantum Computing—What Comes Next? 1908.8 Other Applications of Finite Fields 1929 Why Stop Now? 1999.1 Some Edited Highlights 1999.2 Sizes of Infinity 2009.3 How Many Prime Numbers Are There? 2049.4 Difference Sets, Sequences and Finite Geometry 2069.5 Finite Simple Groups 215Answers to Questions for the Reader 221Further Reading 251Index 257