Yan Primality Testing and Integer Factorization in Public-Key Cryptography

2. Auflage 2009
ISBN: 978-0-387-77268-4
Verlag: Springer US
Format: PDF
Kopierschutz: 1 - PDF Watermark

E-Book, Englisch, Band 11, 371 Seiten

Reihe: Advances in Information Security

Intended for advanced level students in computer science and mathematics, this key text, now in a brand new edition, provides a survey of recent progress in primality testing and integer factorization, with implications for factoring based public key cryptography. For this updated and revised edition, notable new features include a comparison of the Rabin-Miller probabilistic test in RP, the Atkin-Morain elliptic curve test in ZPP and the AKS deterministic test.

Autoren/Hrsg.

Yan, Song Y.

Inhaltsverzeichnis

1;Table of Contents;7
2;Preface to the Second Edition;9
3;Preface to the First Edition;11
3.1;Acknowledgments;12
4;Notation;13
5;1. Number Theoretic Preliminaries;19
5.1;1.1 Problems in Number Theory;19
5.2;Problems for Section 1.1;29
5.3;1.2 Groups, Rings and Fields;31
5.4;Problems for Section 1.2;41
5.5;1.3 Divisibility Properties;41
5.6;Problems for Section 1.3;50
5.7;1.4 Euclid's Algorithm and Continued Fractions;52
5.8;Problems for Section 1.4;67
5.9;1.5 Arithmetic Functions ¾(n); ¿ (n); Á(n); ¸(n); ¹(n);68
5.10;Problems for Section 1.5;79
5.11;1.6 Linear Congruences;81
5.12;Problems for Section 1.6;102
5.13;1.7 Quadratic Congruences;103
5.14;Problems for Section 1.7;120
5.15;1.8 Primitive Roots and Power Residues;121
5.16;Problems for Section 1.8;130
5.17;1.9 Arithmetic of Elliptic Curves;131
5.18;Problems for Section 1.9;141
5.19;1.10 Chapter Notes and Further Reading;142
6;2. Primality Testing and Prime Generation;144
6.1;2.1 Computing with Numbers and Curves;144
6.2;Problems for Section 2.1;155
6.3;2.2 Riemann ³ and Dirichlet L Functions;156
6.4;Problems for Section 2.2;165
6.5;2.3 Rigorous Primality Tests;166
6.6;Problems for Section 2.3;173
6.7;2.4 Compositeness and Pseudoprimality Tests;174
6.8;Problems for Section 2.4;184
6.9;2.5 Lucas Pseudoprimality Test;185
6.10;Problems for Section 2.5;188
6.11;2.6 Elliptic Curve Primality Tests;189
6.12;Problems for Section 2.6;193
6.13;2.7 Superpolynomial-Time Tests;194
6.14;Problems for Section 2.7;198
6.15;2.8 Polynomial-Time Tests;199
6.16;Problems for Section 2.8;203
6.17;2.9 Comparison of General Purpose Primality Tests;205
6.18;Problems for Section 2.9;208
6.19;2.10 Primality Tests for Special Numbers;209
6.20;Problems for Section 2.10;217
6.21;2.11 Prime Number Generation;218
6.22;Problems for Section 2.11;223
6.23;2.12 Chapter Notes and Further Reading;224
7;3. Integer Factorization and Discrete Logarithms;225
7.1;3.1 Introduction;225
7.2;Problems for Section 3.1;227
7.3;3.2 Simple Factoring Methods;228
7.4;Problems for Section 3.2;236
7.5;3.3 Elliptic Curve Method (ECM);237
7.6;Problems for Section 3.3;241
7.7;3.4 General Factoring Congruence;242
7.8;Problems for Section 3.4;245
7.9;3.5 Continued FRACtion Method (CFRAC);246
7.10;Problems for Section 3.5;249
7.11;3.6 Quadratic Sieve (QS);250
7.12;Problems for Section 3.6;254
7.13;3.7 Number Field Sieve (NFS);255
7.14;Problems for Section 3.7;265
7.15;3.8 Quantum Factoring Algorithm;267
7.16;Problems for Section 3.8;272
7.17;3.9 Discrete Logarithms;273
7.18;Problems for Section 3.9;285
7.19;3.10 kth Roots;286
7.20;Problems for Section 3.10;293
7.21;3.11 Elliptic Curve Discrete Logarithms;294
7.22;Problems for Section 3.11;299
7.23;3.12 Chapter Notes and Further Reading;301
8;4. Number-Theoretic Cryptography;302
8.1;4.1 Public-Key Cryptography;302
8.2;Problems for Section 4.1;306
8.3;4.2 RSA Cryptosystem;307
8.4;Problems for Section 4.2;314
8.5;4.3 Security and Cryptanalysis of RSA;316
8.6;Problems for Section 4.3;327
8.7;4.4 Rabin Cryptography;329
8.8;Problems for Section 4.4;334
8.9;4.5 Quadratic Residuosity Cryptography;335
8.10;Problems for Section 4.5;340
8.11;4.6 Discrete Logarithm Cryptography;341
8.12;Problems for Section 4.6;345
8.13;4.7 Elliptic Curve Cryptography;346
8.14;Problems for Section 4.7;352
8.15;4.8 Zero-Knowledge Techniques;353
8.16;Problems for Section 4.8;356
8.17;4.9 Deniable Authentication;356
8.18;Problems for Section 4.9;361
8.19;4.10 Non-Factoring Based Cryptography;361
8.20;Problems for Section 4.10;365
8.21;4.11 Chapter Notes and Further Reading;366
9;Bibliography;367
10;Index;381
10.1;About the Author;386