PREFACE xv

primes; for RSA to be secure, it should be very hard for someone

to factor a given number (even if they’re told it’s just the product

of two primes). Thus, this advanced chapter is a companion to the

RSA chapter, but is not needed to understand the implementation

of RSA. The mathematical requirements of the chapter grow as we

progress further; the first algorithms are elementary, while the last

is the only known modern, provably fast way to determine whether

a number is prime. As there are many primality tests and factoriza-

tion algorithms, there should be a compelling reason behind what

we include and what we omit, and there is. For centuries people

had unsuccessfully searched for a provably fast primality test; the

mathematics community was shocked when Agrawal, Kayal, and

Saxena found just such an algorithm. Our goal is not to prove why

their algorithm works, but instead to explain the ideas and nota-

tion so that the interested reader can pick up the paper and follow

the proof, as well as to remind the reader that just because a prob-

lem seems hard or impossible does not mean that it is! As much

of cryptography is built around the assumption of the diﬃculty of

solving certain problems, this is a lesson worth learning well.

Chapters 1–5 and 10 can be covered as a one semester course in math-

ematics for liberal arts or criminal justice majors, with little or no math-

ematics background. If time permits, parts of Chapters 9 and 11 can be

included or sections from the RSA chapters (Chapters 7 and 8). For a se-

mester course for mathematics, science, or engineering majors, most of the

chapters can be covered in a week or two, which allows a variety of options

to supplement the core material from the first few chapters.

A natural choice is to build the semester with the intention of describing

RSA in complete detail and then supplementing as time allows with topics

from Chapters 9 and 11. Depending on the length of the semester, some

of the classical ciphers can safely be omitted (such as the permutation and

the Hill ciphers), which shortens several of the first few chapters and lessens

the mathematical prerequisites. Other options are to skip either the

Enigma/Ultra chapter (Chapter 3) or the symmetric encryption chapter

(Chapter 6) to have more time for other topics. Chapters 1 and 10 are less

mathematical. These are meant to provide a broad overview of the past,

present, and future of the subject and are thus good chapters for all to read.

Cryptography is a wonderful subject with lots of great applications. It’s

a terrific way to motivate some great mathematics. We hope you enjoy the

journey ahead, and we end with some advice:

• Wzr fdq nhhs d vhfuhw li rqh lv ghdg.

• Zh fdq idfwru wkh qxpehu iliwhhq zlwk txdqwxp frpsxwhuv.

Zh fdq dovr idfwru wkh qxpehu iliwhhq zlwk d grj wudlqhg

wr edun wkuhh wlphv.

• Jlyh xv wkh wrrov dqg zh zloo ilqlvk wkh mre.