Primality testing and integer factorization in public-key cryptography (Q1418120): Difference between revisions

The celebrated 'A Course in Number Theory and Cryptography' of \textit{N. Koblitz} [(New York: Springer-Verlag) (1987; Zbl 0648.10001)] was a seminal book. With the Public-Key Cryptography (in particular the RSA cryptosystem) as \textit{leitmotiv} it brings together the classical results of Elementary Number Theory that are at the basis of RSA, a brief discussion of the computational complexity of the algorithms involved (\textit{The time estimates for doing arithmetic} in the author's words) and the study of two main topics in Computational Algebra: Primality Tests and Integer Factorization. Other books follow that path. In this sense the present book could be considered as a son of Koblitz's book. The scope and structure are similar: after a first chapter of `Number-Theoretic Preliminaries', the chapters 2 and 3 are devoted to present the state of the art in the fields of Primality Testing and Integer Factorization. The last chapter covers the study of the main public-key cryptosystems: RSA, Discrete Logarithm-based Cryptography and Elliptic Curve Cryptography. Of course compared with the \textit{old} book of Koblitz some new results are included in the present book: for instance the AKS algorithm [\textit{Agrawal, Kayal} and \textit{Saxena}, \textit{Prime is in} \({\mathcal P}\), August (2002)], the first deterministic primality test with polynomial complexity, or the quantum factoring method of Shor. The book tries to be self-contained and, in the author's words, ``can be used either as a textbook suitable for a course for final-year undergraduate or first-year postgraduate students, or a basic reference in the field''. Many examples are included through the text but no exercises. At the end of each chapter there are notes and references to the bibliography (181 items).