You are here

A Course in Number Theory and Cryptography

Neal Koblitz
Publication Date: 
Number of Pages: 
Graduate Texts in Mathematics 114
BLL Rating: 

The Basic Library List Committee recommends this book for acquisition by undergraduate mathematics libraries.

[Reviewed by
Allen Stenger
, on

This book suffers from having too many goals: it attempts to be an introduction to both number theory and to cryptography, by studying the overlap between the two subjects, and it attempts to be an introduction to computational number theory. The portion of number theory that is used in cryptography is a minuscule part of all number theory, and reading this book will not give you a good idea of what number theory is about. Cryptography is a large, complex, and rapidly-growing subject, so studying the parts that deal with number theory teaches you only a tiny corner of cryptography. Computational number theory is not a subject most people would be interested in unless they already knew something about number theory, and although the book has reasonable coverage of this topic, it is not well-motivated for the intended reader.

Given these limitations, the book is well done. It is presented as applied number theory, and it does have good coverage of applications, including RSA encryption and primality testing. It has an algorithmic orientation, including estimates of computational costs of all the algorithms. There are lots of numerical examples, although only very simple ones, because the book was published in 1994 and assumes the reader won’t have access to computers. A Very Good Feature is that it includes solutions to all the exercises.

About one-third of the book is devoted to factorization methods, even though these don’t have much, if anything, to do with cryptography, and this is where most of the computational number theory is. The material here is good and still fairly up-to-date. A good book strictly on factorization is David Bressoud’s Factorization and Primality Testing, that covers roughly the same topics in these areas but in more depth.

Allen Stenger is a math hobbyist and retired software developer. He is webmaster and newsletter editor for the MAA Southwestern Section and is an editor of the Missouri Journal of Mathematical Sciences. His mathematical interests are number theory and classical analysis. He volunteers in his spare time at, a math help site that fosters inquiry learning.



  • Foreword
  • Preface to the Second Edition
  • Chapter I. Some Topics in Elementary Number Theory
    1. Time estimates for doing arithmetic
    2. Divisibility and the Euclidean algorithm
    3. Congruences
    4. Some applications to factoring
  • Chapter II. Finite Fields and Quadratic Residues
    1. Finite fields
    2. Quadratic residues and reciprocity
  • Chapter III. Cryptography
    1. Some simple cryptosystems
    2. Enciphering matrices
  • Chapter IV. Public Key
    1. The idea of public key cryptography
    2. RSA
    3. Discrete log
    4. Knapsack
    5. Zero-knowledge protocols and oblivious transfer
  • Chapter V. Primality and Factoring
    1. Pseudoprimes
    2. The rho method
    3. Fermat factorization and factor bases
    4. The continued fraction method
    5. The quadratic sieve method
  • Chapter VI. Elliptic Curves
    1. Basic facts
    2. Elliptic curve cryptosystems
    3. Elliptic curve primality test
    4. Elliptic curve factorization
  • Answers to Exercises
  • Index