Primality Testing and Integer Factorization in Public-Key CryptographyPrimality testing and integer factorization, as identified by Gauss in his "Disquisitiones Arithmeticae", Article 329, in 1801, are the two most fundamental problems (as well as the two most important research fields) in computational number theory. With the advent of modern computers, unexpected applications have also been found in primality testing and integer factorization. Primality Testing and Integer Factorization in Public-Key Cryptography introduces various algorithms for primality testing and integer factorization, with their applications in public-key cryptography and information security. More specifically, this book explores basic concepts and results in number theory in Chapter 1. Chapter 2 discusses various algorithms for primality testing and prime number generation, with an emphasis on the Miller-Rabin probabilistic test, the Goldwasser-Kilian and Atkin-Morain elliptic curve tests, and the Agrawal-Kayal-Saxena deterministic test for primality. Chapter 3 introduces various algorithms, particularly the Elliptic Curve Method (ECM), the Quadratic Sieve (QS) and the Number Field Sieve (NFS) for integer factorization. This chapter also discusses some other computational problems that are related to factoring, such as the square root problem, the discrete logarithm problem and the quadratic residuosity problem. The final chapter presents the applications of the problems/techniques of primality testing, integer factorization, square roots, discrete logarithms and quadratic residuosity in public-key cryptography. Primality Testing and Integer Factorization in Public-Key Cryptography is designed for a professional audience composed of researchers and practitioners in industry. This book is also suitable as a secondary text for graduate-level students in computer science, mathematics and engineering. |
Contents
III | i |
IV | iii |
V | xi |
VI | 9 |
VII | 19 |
VIII | 39 |
IX | 56 |
X | 64 |
XXVI | 133 |
XXVII | 136 |
XXVIII | 139 |
XXIX | 142 |
XXX | 146 |
XXXI | 151 |
XXXII | 154 |
XXXIII | 164 |
XI | 70 |
XII | 81 |
XIII | 83 |
XV | 84 |
XVI | 93 |
XVII | 99 |
XVIII | 102 |
XIX | 109 |
XX | 113 |
XXI | 118 |
XXII | 121 |
XXIII | 123 |
XXV | 125 |
XXXIV | 171 |
XXXV | 175 |
XXXVI | 177 |
XXXVIII | 181 |
XXXIX | 189 |
XL | 194 |
XLI | 198 |
XLII | 203 |
XLIII | 206 |
XLIV | 207 |
XLV | 217 |
Other editions - View all
Primality Testing and Integer Factorization in Public-Key Cryptography Song Y. Yan Limited preview - 2009 |
Primality Testing and Integer Factorization in Public-Key Cryptography Song Y. Yan Limited preview - 2013 |
Primality Testing and Integer Factorization in Public-Key Cryptography Song Y. Yan No preview available - 2010 |
Common terms and phrases
Alice binary called CFRAC classes modulo complexity compute conjecture decryption Definition denoted digits Diophantine equation discrete logarithm problem ECDLP elements elliptic curve discrete encryption Euclid's algorithm Euler's Example factoring algorithm Fermat's little theorem Field Sieve finite field function gcd(a goto hence integer factorization Jacobi symbol large prime Legendre symbol log log mod n mod q nontrivial factor Note Number Field Sieve number theory odd prime P₁ polynomial positive integer primality testing prime factor prime numbers primitive root probable prime Proof pseudoprimality test public-key cryptography public-key cryptosystems quadratic congruence quadratic non-residue quadratic residues quadratic residuosity problem Quadratic Sieve r₁ rational number Re(s relatively prime residue classes Riemann Hypothesis roots modulo RSA cryptosystem satisfies Shiing-Shen Chern simple continued fraction solution solve square root Suppose system of residues Z/nZ