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.

Purchased from American Mathematical Society for the exclusive use of nofirst nolast (email unknown) Copyright 2013 American Mathematical Society. Duplication prohibited. Please report unauthorized use to cust-serv@ams.org. Thank You! Your purchase supports the AMS' mission, programs, and services for the mathematical community.