Mathematics for the Digital Systems Engineer

List of Figures xi
List of Tables xii
About the Author xiii
Preface: Why This Book? xv
Acknowledgements xix
Table of Abbreviations xxi
About the Companion Site xxiii

1 A Gentle Introduction 1
1.1 What Is This Book About? 1
1.2 Mathematics as Mathematicians See It 2
1.3 Theorems and Proofs 5
1.4 Abstract Algebra 8
1.5 What Do You Need to Know to Make Sense of This Book? 9
1.6 Case Studies of Applications 9

2 Sets, Functions and Relations 11
2.1 Why Are Sets Important? 11
2.2 Sets 12
2.3 Cartesian Products of Sets 17
2.4 Relations 17
2.5 Equivalence Relations and Equivalence Classes 18
2.6 Relations: A Detailed Example 21
2.7 Functions 24
2.8 Operations 26

3 Numbers as We Know and Love Them 29
3.1 Where Does Mathematics Start? 29
3.2 The Natural Numbers and the Integers 30
3.3 Writing Down Numbers 32
3.4 Ordering the Integers 33
3.5 Induction 35
3.6 The Division Theorem 38
3.7 Prime Numbers and Common Factors 40
3.8 Unique Factorisation 43
3.9 The Euclidean Algorithm 44
3.10 The Rationals 46
3.11 The Real and Complex Numbers 49
3.12 Applying Complex Numbers-An Everyday Example 50

4 Modular Arithmetic on the Integers 53
4.1 Working Relative to a Modulus 53
4.2 Congruences: Making It More Mathematical 54
4.3 Parity Checks: Using Modulo 2 Arithmetic 57
4.4 Check Digits: A More Complex Example 58
4.5 Elementary Properties of Zn 61
4.6 The Extended Euclidean Algorithm 64
4.7 Cryptography Ancient and Modern 66
4.8 RSA: How Does It Work? 69
4.9 Using RSA 72
4.10 Implementing RSA 75
4.11 RSA and the Future 78
4.12 Other Applications of Modular Arithmetic 79

5 Groups 81
5.1 What Is a Group? 81
5.2 A First Example: The Integers 83
5.3 A Second Example: Modular Addition 84
5.4 But What About Modular Multiplication? 86
5.5 Subgroups and Lagrange's Theorem 89
5.6 Proving Euler's Theorem 92
5.7 Examples of Non-abelian Groups 95
5.8 When Are Two Groups the Same Group? 100
5.9 Combining Groups 104
5.10 Discrete Logarithms 106
5.11 Diffie-Hellman Key Agreement 108
5.12 Other Applications of Discrete Logarithms 112
5.13 The Threat Posed by Quantum Computing 112
5.14 Other Applications of Groups 114

6 Rings and Fields 117
6.1 Two Operations, Not Just One! 117
6.2 So What Is a Ring? 118
6.3 Types of Rings 120
6.4 Combining Rings 122
6.5 Integral Domains-Some Key Properties 124
6.6 Unique Factorisation Domains-Key Properties 127
6.7 When Are Two Rings the Same Ring? 127
6.8 Fields 130
6.9 Coding Theory 135

7 Polynomials and Polynomial Rings 145
7.1 What Do I Mean by Polynomials? 145
7.2 Doing Arithmetic with Polynomials 149
7.3 Polynomials over a Field 151
7.4 Shift Register Sequences 154
7.5 Polynomial Arithmetic Modulo a Polynomial 168

8 Finite Fields 175
8.1 The Core of the Book 175
8.2 The Prime Fields 176
8.3 How Many Elements Might There Be? 176
8.4 Prime Power Fields 177
8.5 Uniqueness and Representation of Finite Fields 180
8.6 Elliptic Curve Cryptography 181
8.7 Quantum Computing-What Comes Next? 190
8.8 Other Applications of Finite Fields 192

9 Why Stop Now? 199
9.1 Some Edited Highlights 199
9.2 Sizes of Infinity 200
9.3 How Many Prime Numbers Are There? 204
9.4 Difference Sets, Sequences and Finite Geometry 206
9.5 Finite Simple Groups 215

Answers to Questions for the Reader 221
Further Reading 251
Index 257