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.