Cryptology and error correction

✍ Scribed by Childs L.N

• Publisher: Springer
• Year: 2019
• Tongue: English
• Leaves: 353
• Series: SUMAT
• Category: Library

✦ Table of Contents

Preface......Page 6
Origin of This Book......Page 9
Acknowledgements......Page 10
Contents......Page 11
1.1 Introduction......Page 15
1.2 Least Non-negative Residues and Clock Arithmetic......Page 16
1.3 Cryptography......Page 17
1.4 Error Detection and Correction......Page 21
2.1 Arithmetic Modulo m......Page 26
2.2 Modular Arithmetic and Encryption......Page 30
2.3 Congruence Modulo m......Page 32
2.4 Letters to Numbers......Page 35
3 Linear Equations Modulo m......Page 40
3.1 The Greatest Common Divisor......Page 41
3.2 Finding the Greatest Common Divisor......Page 43
3.3 Bezout's Identity......Page 46
3.4 Finding Bezout's Identity......Page 48
3.5 The Coprime Divisibility Lemma......Page 54
3.6 Solutions of Linear Diophantine Equations......Page 55
3.7 Manipulating and Solving Linear Congruences......Page 58
4.1 Unique Factorization into Products of Prime Numbers......Page 63
4.2 Induction......Page 68
4.3 The Fundamental Theorem of Arithmetic......Page 70
4.4 The Division Theorem......Page 72
4.5 Well-Ordering......Page 73
5 Rings and Fields......Page 77
5.1 Groups, Commutative Rings, Fields, Units......Page 78
5.2 Basic Properties of Groups and Rings......Page 79
5.3 Units and Fields......Page 81
5.4 Ideals......Page 82
5.5 Cosets and Integers Modulo m......Page 85
5.6 mathbbZm is a Commutative Ring......Page 88
5.7 Complete Sets of Representatives for mathbbZ/mmathbbZ......Page 90
5.8 When is mathbbZ/mmathbbZ a Field?......Page 91
6.1 Basic Concepts......Page 95
6.2 Division Theorem......Page 98
6.3 D'Alembert's Theorem......Page 100
7.1 Matrices and Vectors......Page 104
7.2 Error Correcting and Detecting Codes......Page 112
7.3 The Hamming (7, 4) Code: A Single Error Correcting Code......Page 113
7.4 The Hamming (8, 4) Code......Page 119
7.5 Why Do These Codes Work?......Page 121
8.1 Orders of Elements......Page 127
8.2 Fermat's Theorem......Page 131
8.3 Euler's Theorem......Page 133
8.4 The Binomial Theorem and Fermat's Theorem......Page 135
8.5 Finding High Powers Modulo m......Page 137
9.1 RSA Cryptography......Page 144
9.2 Why Is RSA Effective?......Page 147
9.3 Signatures......Page 149
9.5 There are Many Large Primes......Page 150
9.6 Finding Large Primes......Page 152
9.7 The a-Pseudoprime Test......Page 153
9.8 The Strong a-Pseudoprime Test......Page 155
10.1 Groups......Page 161
10.2 Subgroups......Page 162
10.4 Cosets......Page 168
10.5 Lagrange's Theorem......Page 173
10.6 Non-abelian Groups......Page 175
11 Solving Systems of Congruences......Page 178
11.1 Two Congruences: The ``Linear Combination'' Method......Page 179
11.2 More Than Two Congruences......Page 183
11.3 Some Applications to RSA Cryptography......Page 184
11.4 Solving General Systems of Congruences......Page 188
11.5 Solving Two Congruences......Page 189
11.6 Three or More Congruences......Page 193
11.7 Systems of Non-monic Linear Congruences......Page 194
12.1 The Formulas for Euler's Phi Function......Page 201
12.2 On Functions......Page 202
12.3 Ring Homomorphisms......Page 203
12.4 Fundamental Homomorphism Theorem......Page 206
12.5 Group Homomorphisms......Page 207
12.6 The Product of Rings and the Chinese Remainder Theorem......Page 210
12.7 Units and Euler's Formula......Page 214
13.1 Cyclic Groups......Page 220
13.2 The Discrete Logarithm......Page 222
13.3 Diffie–Hellman Key Exchange......Page 225
13.4 ElGamal Cryptography......Page 226
13.5 Diffie–Hellman in Practice......Page 227
13.6 The Exponent of an Abelian Group......Page 229
13.7 The Primitive Root Theorem......Page 233
13.8 The Exponent of Um......Page 235
13.9 The Pohlig–Hellman Algorithm......Page 236
13.10 Shanks' Baby Step-Giant Step Algorithm......Page 238
14.1 Group Homomorphisms, Cosets and Non-homogeneous Equations......Page 245
14.2 On Hamming Codes......Page 250
14.3 Euler's Theorem......Page 252
14.4 A Probabilistic Compositeness Test......Page 254
14.5 There Are No Strong Carmichael Numbers......Page 255
14.6 Boneh's Theorem......Page 257
15.1 The Setting......Page 262
15.2 Encoding a Reed–Solomon Code......Page 263
15.3 Decoding......Page 266
15.4 An Example......Page 269
16.1 Vernam Cryptosystems......Page 276
16.2 Blum, Blum and Shub's Pseudorandom Number Generator......Page 278
16.3 Blum-Goldwasser Cryptography......Page 279
16.4 The Period of a BBS Sequence......Page 281
16.5 Recreating a BBS Sequence from the Last Term......Page 285
16.6 Security of the B-G Cryptosystem......Page 286
16.7 Implementation of the Blum-Goldwasser Cryptosystem......Page 289
17.1 Trial Division......Page 296
17.2 The Basic Idea Behind the Quadratic Sieve Method......Page 297
17.3 Fermat's Method of Factoring......Page 299
17.4 The Quadratic Sieve Method......Page 300
17.5 The Index Calculus Method for Discrete Logarithms......Page 309
18.1 Greatest Common Divisors......Page 316
18.2 Factorization into Irreducible Polynomials......Page 320
18.3 Ideals of F[x]......Page 323
18.4 Cosets and Quotient Rings......Page 324
18.5 Constructing Many Finite Fields......Page 329
19.1 Roots of Unity and the Discrete Fourier Transform......Page 334
19.2 A Field with 8 Elements......Page 336
19.3 A Reed-Solomon Code Using mathbbF8......Page 337
19.4 An Example Using mathbbF13......Page 340
BookmarkTitle:......Page 346
Index......Page 349