Primality Testing and Integer Factorization in Public-Key Cryptography (eBook)

Table of Contents 7
Preface to the Second Edition 9
Preface to the First Edition 11
Acknowledgments 12
Notation 13
1. Number Theoretic Preliminaries 19
1.1 Problems in Number Theory 19
Problems for Section 1.1 29
1.2 Groups, Rings and Fields 31
Problems for Section 1.2 41
1.3 Divisibility Properties 41
Problems for Section 1.3 50
1.4 Euclid's Algorithm and Continued Fractions 52
Problems for Section 1.4 67
1.5 Arithmetic Functions ¾(n) ¿ (n)
Problems for Section 1.5 79
1.6 Linear Congruences 81
Problems for Section 1.6 102
1.7 Quadratic Congruences 103
Problems for Section 1.7 120
1.8 Primitive Roots and Power Residues 121
Problems for Section 1.8 130
1.9 Arithmetic of Elliptic Curves 131
Problems for Section 1.9 141
1.10 Chapter Notes and Further Reading 142
2. Primality Testing and Prime Generation 144
2.1 Computing with Numbers and Curves 144
Problems for Section 2.1 155
2.2 Riemann ³ and Dirichlet L Functions 156
Problems for Section 2.2 165
2.3 Rigorous Primality Tests 166
Problems for Section 2.3 173
2.4 Compositeness and Pseudoprimality Tests 174
Problems for Section 2.4 184
2.5 Lucas Pseudoprimality Test 185
Problems for Section 2.5 188
2.6 Elliptic Curve Primality Tests 189
Problems for Section 2.6 193
2.7 Superpolynomial-Time Tests 194
Problems for Section 2.7 198
2.8 Polynomial-Time Tests 199
Problems for Section 2.8 203
2.9 Comparison of General Purpose Primality Tests 205
Problems for Section 2.9 208
2.10 Primality Tests for Special Numbers 209
Problems for Section 2.10 217
2.11 Prime Number Generation 218
Problems for Section 2.11 223
2.12 Chapter Notes and Further Reading 224
3. Integer Factorization and Discrete Logarithms 225
3.1 Introduction 225
Problems for Section 3.1 227
3.2 Simple Factoring Methods 228
Problems for Section 3.2 236
3.3 Elliptic Curve Method (ECM) 237
Problems for Section 3.3 241
3.4 General Factoring Congruence 242
Problems for Section 3.4 245
3.5 Continued FRACtion Method (CFRAC) 246
Problems for Section 3.5 249
3.6 Quadratic Sieve (QS) 250
Problems for Section 3.6 254
3.7 Number Field Sieve (NFS) 255
Problems for Section 3.7 265
3.8 Quantum Factoring Algorithm 267
Problems for Section 3.8 272
3.9 Discrete Logarithms 273
Problems for Section 3.9 285
3.10 kth Roots 286
Problems for Section 3.10 293
3.11 Elliptic Curve Discrete Logarithms 294
Problems for Section 3.11 299
3.12 Chapter Notes and Further Reading 301
4. Number-Theoretic Cryptography 302
4.1 Public-Key Cryptography 302
Problems for Section 4.1 306
4.2 RSA Cryptosystem 307
Problems for Section 4.2 314
4.3 Security and Cryptanalysis of RSA 316
Problems for Section 4.3 327
4.4 Rabin Cryptography 329
Problems for Section 4.4 334
4.5 Quadratic Residuosity Cryptography 335
Problems for Section 4.5 340
4.6 Discrete Logarithm Cryptography 341
Problems for Section 4.6 345
4.7 Elliptic Curve Cryptography 346
Problems for Section 4.7 352
4.8 Zero-Knowledge Techniques 353
Problems for Section 4.8 356
4.9 Deniable Authentication 356
Problems for Section 4.9 361
4.10 Non-Factoring Based Cryptography 361
Problems for Section 4.10 365
4.11 Chapter Notes and Further Reading 366
Bibliography 367
Index 381
About the Author 386