Computational Number Theory and Modern Cryptography
Published on 28. November 2012
432 pages
978-1-118-18861-3 (ISBN)
Description
The only book to provide a unified view of the interplay betweencomputational number theory and cryptography
Computational number theory and modern cryptography are two ofthe most important and fundamental research fields in informationsecurity. In this book, Song Y. Yang combines knowledge of thesetwo critical fields, providing a unified view of the relationshipsbetween computational number theory and cryptography. The authortakes an innovative approach, presenting mathematical ideas first,thereupon treating cryptography as an immediate application of themathematical concepts. The book also presents topics from numbertheory, which are relevant for applications in public-keycryptography, as well as modern topics, such as coding and latticebased cryptography for post-quantum cryptography. The authorfurther covers the current research and applications for commoncryptographic algorithms, describing the mathematical problemsbehind these applications in a manner accessible to computerscientists and engineers.
* Makes mathematical problems accessible to computer scientistsand engineers by showing their immediate application
* Presents topics from number theory relevant for public-keycryptography applications
* Covers modern topics such as coding and lattice basedcryptography for post-quantum cryptography
* Starts with the basics, then goes into applications and areasof active research
* Geared at a global audience; classroom tested in North America,Europe, and Asia
* Incudes exercises in every chapter
* Instructor resources available on the book's CompanionWebsite
Computational Number Theory and Modern Cryptography isideal for graduate and advanced undergraduate students incomputer science, communications engineering, cryptography andmathematics. Computer scientists, practicing cryptographers, andother professionals involved in various security schemes will alsofind this book to be a helpful reference.
More details
Other editions
Additional editions
Book
01/2013
Wiley
€108.50
Article exhausted; check different version
Person
Song Y. Yan, Massachusetts Institute of Technology, USA
Song Y. Yan is a Professor in the Department of Mathematics at the Massachusetts Institute of Technology (MIT) and Harvard University. Song is a computer scientist as well as a mathematician whose primary research interests are in the intersection of Mathematics/Number Theory and Computer Science/Information Technology, including areas such as Complexity Theory, Design and Analysis of Algorithms, Cryptography, and Information Security. He is a well-known author in the area, having published 5 books. He obtained a Doctorate in Mathematics (Number Theory) from the Department of Mathematics at the University of York, and majored in both computer science and mathematics.
Content
About the Author ix
Preface xi
Acknowledgments xiii
Part I Preliminaries
1 Introduction 3
1.1 What is Number Theory? 3
1.2 What is Computation Theory? 9
1.3 What is Computational Number Theory? 15
1.4 What is Modern Cryptography? 29
1.5 Bibliographic Notes and Further Reading 32
References 32
2 Fundamentals 35
2.1 Basic Algebraic Structures 35
2.2 Divisibility Theory 46
2.3 Arithmetic Functions 75
2.4 Congruence Theory 89
2.5 Primitive Roots 131
2.6 Elliptic Curves 141
2.7 Bibliographic Notes and Further Reading 154
References 155
Part II Computational Number Theory
3 Primality Testing 159
3.1 Basic Tests 159
3.2 Miller-Rabin Test 168
3.3 Elliptic Curve Tests 173
3.4 AKS Test 178
3.5 Bibliographic Notes and Further Reading 187
References 188
4 Integer Factorization 191
4.1 Basic Concepts 191
4.2 Trial Divisions Factoring 194
4.3 rho and p - 1 Methods 198
4.4 Elliptic Curve Method 205
4.5 Continued Fraction Method 209
4.6 Quadratic Sieve 214
4.7 Number Field Sieve 219
4.8 Bibliographic Notes and Further Reading 231
References 232
5 Discrete Logarithms 235
5.1 Basic Concepts 235
5.2 Baby-Step Giant-Step Method 237
5.3 Pohlig-Hellman Method 240
5.4 Index Calculus 246
5.5 Elliptic Curve Discrete Logarithms 251
5.6 Bibliographic Notes and Further Reading 260
References 261
Part III Modern Cryptography
6 Secret-Key Cryptography 265
6.1 Cryptography and Cryptanalysis 265
6.2 Classic Secret-Key Cryptography 277
6.3 Modern Secret-Key Cryptography 285
6.4 Bibliographic Notes and Further Reading 291
References 291
7 Integer Factorization Based Cryptography 293
7.1 RSA Cryptography 293
7.2 Cryptanalysis of RSA 302
7.3 Rabin Cryptography 319
7.4 Residuosity Based Cryptography 326
7.5 Zero-Knowledge Proof 331
7.6 Bibliographic Notes and Further Reading 335
References 335
8 Discrete Logarithm Based Cryptography 337
8.1 Diffie-Hellman-Merkle Key-Exchange Protocol337
8.2 ElGamal Cryptography 342
8.3 Massey-Omura Cryptography 344
8.4 DLP-Based Digital Signatures 348
8.5 Bibliographic Notes and Further Reading 351
References 351
9 Elliptic Curve Discrete Logarithm Based Cryptography 353
9.1 Basic Ideas 353
9.2 Elliptic Curve Diffie-Hellman-Merkle KeyExchange Scheme 356
9.3 Elliptic Curve Massey-Omura Cryptography 360
9.4 Elliptic Curve ElGamal Cryptography 365
9.5 Elliptic Curve RSA Cryptosystem 370
9.6 Menezes-Vanstone Elliptic Curve Cryptography 371
9.7 Elliptic Curve DSA 373
9.8 Bibliographic Notes and Further Reading 374
References 375
Part IV Quantum Resistant Cryptography
10 Quantum Computational Number Theory 379
10.1 Quantum Algorithms for Order Finding 379
10.2 Quantum Algorithms for Integer Factorization 385
10.3 Quantum Algorithms for Discrete Logarithms 390
10.4 Quantum Algorithms for Elliptic Curve Discrete Logarithms393
10.5 Bibliographic Notes and Further Reading 397
References 397
11 Quantum Resistant Cryptography 401
11.1 Coding-Based Cryptography 401
11.2 Lattice-Based Cryptography 403
11.3 Quantum Cryptography 404
11.4 DNA Biological Cryptography 406
11.5 Bibliographic Notes and Further Reading 409
References 410
Index 413
