Browse Books

Reviewer: Marlene L. Campbell

Koblitz begins by immediately discussing bit operations and big- O notation and its relation to algorithm complexity. Basic number theory topics are introduced rather systematically. Material is well presented in reasonable-sized blocks that are followed by exercises that vary from some brute force manipulations to thought provoking and challenging analyses and proofs. Since answers to the exercises are provided, the book could, indeed, be used for independent study by a serious, motivated student with a reasonable background in number theory and abstract algebra who is experienced in problem solving. It is not a book for the faint of heart. Chapter 1, “some topics in elementary number theory,” is a bit more comprehensible than chapter 2, “finite fields and quadratic residues.” Although there is a minimal use of thorough explanations and examples in the first two chapters, the understanding of early introduced theorems, corollaries, propositions, and lemmas is enhanced by the orderly progression of topics along with the application and extension of previously introduced notions. It is evident that the author's presentation of material was influenced by the proliferation of computer power and sophistication. As stated in the forward, these technological advances have given rise to a new branch of number theory called computational number theory. Unlike the first two chapters, chapter 3, “cryptography,” assumes no prior knowledge of this particular subject and starts with the basics. This is done in a thorough manner (i.e., by defining terms, explaining fundamental concepts, and using elementary examples before building to more elegant ones). Koblitz first presents an affine cryptosystem in an N-letter alphabet with parameters a ? ( Z/ NZ) 2* and b ? Z/ NZ consisting of the rules: C ? a P + b mod N, and P ? a? C + b? mod N, where a? = a ?1 in ( Z/ NZ)*, and b? = ? a ?1 b. After discussing the special cases of this cryptosystem, which result in a shift transformation and a linear transformation, he provides nice examples and follows with an abundance of exercises. He quickly moves on to enciphering matrices but takes time to review elementary concepts of linear algebra and matrix multiplication before pursuing this cryptosystem. After each cryptosystem is presented, he presents tactics used in the cryptanalysis of the systems. In the first three chapters, references are included at the end of each chapter; but the remaining chapters, 4 through 6, include both exercises and references after each main subsection of the chapters. Chapter 4, “public key,” begins with a general discussion of the concept of public keys and digital signatures and leaves the details of the procedures to the remaining subsections. The discussion of the RSA cryptosystem does a good job of presenting the whys and hows. Other methods presented in the chapter include the discrete logarithm problem, the Diffie-Hellman key exchange system, the Massey-Omura cryptosystem for message transmission, and the El Gamal cryptosystem and algorithms for finding discrete logs in finite fields. I was a bit surprised to find no mention of the Data Encryption Standard although it has recently come through its second five-year review. Both chapters 5 and 6, “primality and factoring” and “elliptic curves,” are handled much like chapter 4. The underlying notions and definitions are presented and then followed by specific applications. Chapter 5 includes a discussion of both primes and pseudoprimes, including Carmichael numbers, Euler pseudoprimes, and strong pseudoprimes. Definitions are given, propositions regarding these defined terms are proved, and examples are used to clarify the concepts. In addition to various primality tests, the author presents factorization methods, including the rho method (also called the Monte Carlo method), Fermat factorization, and a factor base algorithm, together with its heuristic time estimate. He concludes the chapter with a discussion of continued fractions and the continued fraction factoring algorithms. In chapter 6, Koblitz points out that the theory of elliptic curves defined over finite fields has recently found application in cryptography. He presents basic definitions and facts about elliptic curves including only “the minimal amount of background necessary to understand the applications to cryptography . . . emphasizing examples and concrete descriptions at the expense of proofs and generality.” This, I believe, is a good decision for this particular textbook. The reader wishing to learn more can consult the various references following the sections on elliptic curve cryptosystems and elliptic curve factorization. As the title indicates, the book is intended for use in a graduate mathematics course in number theory and cryptography. It would definitely fulfill this mission. The overall content is quite good, the format of the book is traditional, and the index, references, and exercises are fully adequate. The author's recommendations for organizing courses based on the book seem reasonable. I liked the book. I think it has a place not only in a graduate course in mathematics, but also in a graduate course in computer science. It could be used as the basis for a three-hour course in either discipline, or subsets could be used in a readings or special topics course of anywhere from one to three hours. Chapter 3 could be assigned for background reading even at the upper-division undergraduate level. The book would definitely be an asset to the professional reading collection in any undergraduate or graduate library.