Song Y. Yan, North China University of Technology, P.R. China and Harvard University, USA

• About the Author ixPreface xiAcknowledgments xiiiPart I Preliminaries1 Introduction 31.1 What is Number Theory? 31.2 What is Computation Theory? 91.3 What is Computational Number Theory? 151.4 What is Modern Cryptography? 291.5 Bibliographic Notes and Further Reading 32References 322 Fundamentals 352.1 Basic Algebraic Structures 352.2 Divisibility Theory 462.3 Arithmetic Functions 752.4 Congruence Theory 892.5 Primitive Roots 1312.6 Elliptic Curves 1412.7 Bibliographic Notes and Further Reading 154References 155Part II Computational Number Theory3 Primality Testing 1593.1 Basic Tests 1593.2 Miller–Rabin Test 1683.3 Elliptic Curve Tests 1733.4 AKS Test 1783.5 Bibliographic Notes and Further Reading 187References 1884 Integer Factorization 1914.1 Basic Concepts 1914.2 Trial Divisions Factoring 1944.3 ρ and p − 1 Methods 1984.4 Elliptic Curve Method 2054.5 Continued Fraction Method 2094.6 Quadratic Sieve 2144.7 Number Field Sieve 2194.8 Bibliographic Notes and Further Reading 231References 2325 Discrete Logarithms 2355.1 Basic Concepts 2355.2 Baby-Step Giant-Step Method 2375.3 Pohlig–Hellman Method 2405.4 Index Calculus 2465.5 Elliptic Curve Discrete Logarithms 2515.6 Bibliographic Notes and Further Reading 260References 261Part III Modern Cryptography6 Secret-Key Cryptography 2656.1 Cryptography and Cryptanalysis 2656.2 Classic Secret-Key Cryptography 2776.3 Modern Secret-Key Cryptography 2856.4 Bibliographic Notes and Further Reading 291References 2917 Integer Factorization Based Cryptography 2937.1 RSA Cryptography 2937.2 Cryptanalysis of RSA 3027.3 Rabin Cryptography 3197.4 Residuosity Based Cryptography 3267.5 Zero-Knowledge Proof 3317.6 Bibliographic Notes and Further Reading 335References 3358 Discrete Logarithm Based Cryptography 3378.1 Diffie–Hellman–Merkle Key-Exchange Protocol 3378.2 ElGamal Cryptography 3428.3 Massey–Omura Cryptography 3448.4 DLP-Based Digital Signatures 3488.5 Bibliographic Notes and Further Reading 351References 3519 Elliptic Curve Discrete Logarithm Based Cryptography 3539.1 Basic Ideas 3539.2 Elliptic Curve Diffie–Hellman–Merkle Key Exchange Scheme 3569.3 Elliptic Curve Massey–Omura Cryptography 3609.4 Elliptic Curve ElGamal Cryptography 3659.5 Elliptic Curve RSA Cryptosystem 3709.6 Menezes–Vanstone Elliptic Curve Cryptography 3719.7 Elliptic Curve DSA 3739.8 Bibliographic Notes and Further Reading 374References 375Part IV Quantum Resistant Cryptography10 Quantum Computational Number Theory 37910.1 Quantum Algorithms for Order Finding 37910.2 Quantum Algorithms for Integer Factorization 38510.3 Quantum Algorithms for Discrete Logarithms 39010.4 Quantum Algorithms for Elliptic Curve Discrete Logarithms 39310.5 Bibliographic Notes and Further Reading 397References 39711 Quantum Resistant Cryptography 40111.1 Coding-Based Cryptography 40111.2 Lattice-Based Cryptography 40311.3 Quantum Cryptography 40411.4 DNA Biological Cryptography 40611.5 Bibliographic Notes and Further Reading 409References 410Index 413

Song Y. Yan, North China University of Technology, P.R. China and Harvard University, USA

• About the Author ixPreface xiAcknowledgments xiiiPart I Preliminaries1 Introduction 31.1 What is Number Theory? 31.2 What is Computation Theory? 91.3 What is Computational Number Theory? 151.4 What is Modern Cryptography? 291.5 Bibliographic Notes and Further Reading 32References 322 Fundamentals 352.1 Basic Algebraic Structures 352.2 Divisibility Theory 462.3 Arithmetic Functions 752.4 Congruence Theory 892.5 Primitive Roots 1312.6 Elliptic Curves 1412.7 Bibliographic Notes and Further Reading 154References 155Part II Computational Number Theory3 Primality Testing 1593.1 Basic Tests 1593.2 Miller–Rabin Test 1683.3 Elliptic Curve Tests 1733.4 AKS Test 1783.5 Bibliographic Notes and Further Reading 187References 1884 Integer Factorization 1914.1 Basic Concepts 1914.2 Trial Divisions Factoring 1944.3 ρ and p − 1 Methods 1984.4 Elliptic Curve Method 2054.5 Continued Fraction Method 2094.6 Quadratic Sieve 2144.7 Number Field Sieve 2194.8 Bibliographic Notes and Further Reading 231References 2325 Discrete Logarithms 2355.1 Basic Concepts 2355.2 Baby-Step Giant-Step Method 2375.3 Pohlig–Hellman Method 2405.4 Index Calculus 2465.5 Elliptic Curve Discrete Logarithms 2515.6 Bibliographic Notes and Further Reading 260References 261Part III Modern Cryptography6 Secret-Key Cryptography 2656.1 Cryptography and Cryptanalysis 2656.2 Classic Secret-Key Cryptography 2776.3 Modern Secret-Key Cryptography 2856.4 Bibliographic Notes and Further Reading 291References 2917 Integer Factorization Based Cryptography 2937.1 RSA Cryptography 2937.2 Cryptanalysis of RSA 3027.3 Rabin Cryptography 3197.4 Residuosity Based Cryptography 3267.5 Zero-Knowledge Proof 3317.6 Bibliographic Notes and Further Reading 335References 3358 Discrete Logarithm Based Cryptography 3378.1 Diffie–Hellman–Merkle Key-Exchange Protocol 3378.2 ElGamal Cryptography 3428.3 Massey–Omura Cryptography 3448.4 DLP-Based Digital Signatures 3488.5 Bibliographic Notes and Further Reading 351References 3519 Elliptic Curve Discrete Logarithm Based Cryptography 3539.1 Basic Ideas 3539.2 Elliptic Curve Diffie–Hellman–Merkle Key Exchange Scheme 3569.3 Elliptic Curve Massey–Omura Cryptography 3609.4 Elliptic Curve ElGamal Cryptography 3659.5 Elliptic Curve RSA Cryptosystem 3709.6 Menezes–Vanstone Elliptic Curve Cryptography 3719.7 Elliptic Curve DSA 3739.8 Bibliographic Notes and Further Reading 374References 375Part IV Quantum Resistant Cryptography10 Quantum Computational Number Theory 37910.1 Quantum Algorithms for Order Finding 37910.2 Quantum Algorithms for Integer Factorization 38510.3 Quantum Algorithms for Discrete Logarithms 39010.4 Quantum Algorithms for Elliptic Curve Discrete Logarithms 39310.5 Bibliographic Notes and Further Reading 397References 39711 Quantum Resistant Cryptography 40111.1 Coding-Based Cryptography 40111.2 Lattice-Based Cryptography 40311.3 Quantum Cryptography 40411.4 DNA Biological Cryptography 40611.5 Bibliographic Notes and Further Reading 409References 410Index 413

Song Y. Yan, North China University of Technology, P.R. China and Harvard University, USA

• About the Author ixPreface xiAcknowledgments xiiiPart I Preliminaries1 Introduction 31.1 What is Number Theory? 31.2 What is Computation Theory? 91.3 What is Computational Number Theory? 151.4 What is Modern Cryptography? 291.5 Bibliographic Notes and Further Reading 32References 322 Fundamentals 352.1 Basic Algebraic Structures 352.2 Divisibility Theory 462.3 Arithmetic Functions 752.4 Congruence Theory 892.5 Primitive Roots 1312.6 Elliptic Curves 1412.7 Bibliographic Notes and Further Reading 154References 155Part II Computational Number Theory3 Primality Testing 1593.1 Basic Tests 1593.2 Miller–Rabin Test 1683.3 Elliptic Curve Tests 1733.4 AKS Test 1783.5 Bibliographic Notes and Further Reading 187References 1884 Integer Factorization 1914.1 Basic Concepts 1914.2 Trial Divisions Factoring 1944.3 ρ and p − 1 Methods 1984.4 Elliptic Curve Method 2054.5 Continued Fraction Method 2094.6 Quadratic Sieve 2144.7 Number Field Sieve 2194.8 Bibliographic Notes and Further Reading 231References 2325 Discrete Logarithms 2355.1 Basic Concepts 2355.2 Baby-Step Giant-Step Method 2375.3 Pohlig–Hellman Method 2405.4 Index Calculus 2465.5 Elliptic Curve Discrete Logarithms 2515.6 Bibliographic Notes and Further Reading 260References 261Part III Modern Cryptography6 Secret-Key Cryptography 2656.1 Cryptography and Cryptanalysis 2656.2 Classic Secret-Key Cryptography 2776.3 Modern Secret-Key Cryptography 2856.4 Bibliographic Notes and Further Reading 291References 2917 Integer Factorization Based Cryptography 2937.1 RSA Cryptography 2937.2 Cryptanalysis of RSA 3027.3 Rabin Cryptography 3197.4 Residuosity Based Cryptography 3267.5 Zero-Knowledge Proof 3317.6 Bibliographic Notes and Further Reading 335References 3358 Discrete Logarithm Based Cryptography 3378.1 Diffie–Hellman–Merkle Key-Exchange Protocol 3378.2 ElGamal Cryptography 3428.3 Massey–Omura Cryptography 3448.4 DLP-Based Digital Signatures 3488.5 Bibliographic Notes and Further Reading 351References 3519 Elliptic Curve Discrete Logarithm Based Cryptography 3539.1 Basic Ideas 3539.2 Elliptic Curve Diffie–Hellman–Merkle Key Exchange Scheme 3569.3 Elliptic Curve Massey–Omura Cryptography 3609.4 Elliptic Curve ElGamal Cryptography 3659.5 Elliptic Curve RSA Cryptosystem 3709.6 Menezes–Vanstone Elliptic Curve Cryptography 3719.7 Elliptic Curve DSA 3739.8 Bibliographic Notes and Further Reading 374References 375Part IV Quantum Resistant Cryptography10 Quantum Computational Number Theory 37910.1 Quantum Algorithms for Order Finding 37910.2 Quantum Algorithms for Integer Factorization 38510.3 Quantum Algorithms for Discrete Logarithms 39010.4 Quantum Algorithms for Elliptic Curve Discrete Logarithms 39310.5 Bibliographic Notes and Further Reading 397References 39711 Quantum Resistant Cryptography 40111.1 Coding-Based Cryptography 40111.2 Lattice-Based Cryptography 40311.3 Quantum Cryptography 40411.4 DNA Biological Cryptography 40611.5 Bibliographic Notes and Further Reading 409References 410Index 413