zbMATH — the first resource for mathematics

A course in number theory and cryptography. (English) Zbl 0648.10001
Graduate Texts in Mathematics, 114. New York etc.: Springer-Verlag. viii, 208 p.; DM 74.00 (1987).
The difficulty of factoring large numbers has been exploited, as is widely known now, in the public key cryptosystem (RSA) devised by Rivest, Shamir and Adleman [W. Diffie and M. E. Hellmann, New directions in cryptography, IEEE Trans. Inf. Theory IT-22, 644-654 (1976; Zbl 0435.94018); L. M. Adleman, R. L. Rivest and A. Shamir, A method for obtaining digital signatures and public-key cryptosystems, Commun. ACM 21, 120-126 (1978; Zbl 0368.94005)]. This discovery has considerably influenced both cryptography and computational number theory in the past ten years. The book under review presents material needed to gain a thorough understanding of these developments. In the author’s words (Foreword): “Its purpose is to introduce the reader to arithmetic topics, both ancient and very modern, which have been at the center of interest in applications, especially in cryptography. For this reason we take an algorithmic approach, emphasizing estimates of the efficiency of the techniques that arise from the theory.”
Chapter I treats some basic topics in elementary number theory (divisibility, congruences) needed in subsequent chapters. Chapter II introduces finite fields and quadratic residues (with the Law of Quadratic Reciprocity). In chapter III basic notions from cryptography are presented including some simple crypto-systems and enciphering matrices. In chapter IV, the idea of public key cryptography is introduced, followed by a description of three main examples of public key cryptosystems: RSA, discrete log and knapsack.
Chapter V is entitled: “Primality and Factoring”, and treats probabilistic primality tests, and factoring methods like Pollard’s “rho method” and methods based on finding an expression as a difference of squares for the number to be factored (or for a multiple of this number). In the final chapter the author presents the basic definitions and facts about elliptic curves followed by a description of some cryptosystems based on elliptic curves and, finally, H. W. Lenstra’s famous elliptic curve factorization method.
About 230 exercises are scattered throughout the text (with 24 pages of answers at the end). These are extremely helpful to the reader in order to test his or her understanding of the material.
Each chapter or section of a chapter contains a number of references. One small inconsistency: Chapter I refers to the second edition (1978) and Chapter II to the third editon (1985) of D. Shanks’ book: “Unsolved Problems in Number Theory”. The book is carefully written and the reviewer has found only a few minor errors. On page 162, line 10, “2(2(1+2(2(2(1+2P)))))” should read “2(2(p+2(2(2(P+2P)))))”. On page 4 an upper bound for the number of bit operations needed for the multiplication of a k-bit integer by an \(\ell\)-bit integer is given to be \(2k\ell\). By a simple refinement of the argument this bound may be lowered to \((3/2)k\ell.\)
{For readers of the book it may be interesting to know the best practical results with the best known primality testing and factorization methods. An excellent source for this is the book: J. Brillhart, D. H. Lehmer, J. L. Selfridge, B. Tuckerman and S. S. Wagstaff jun., Factorizations of b \(n\pm 1\), Second Edition, Contemp. Math. 22 (1988) (1st ed. 1983; Zbl 0527.10001). Updates to the ‘Tables’ of factored numbers in this book are regularly distributed by S. S. Wagstaff.}
Reviewer: H.J.J.te Riele

11-01 Introductory exposition (textbooks, tutorial papers, etc.) pertaining to number theory
94-01 Introductory exposition (textbooks, tutorial papers, etc.) pertaining to information and communication theory
11-04 Software, source code, etc. for problems pertaining to number theory
11A41 Primes
94A60 Cryptography
14H52 Elliptic curves
68Q25 Analysis of algorithms and problem complexity
11A07 Congruences; primitive roots; residue systems