Mathematics 116
Spring, 2012
Tu Th 9:40AM-11:00 AM, 9 Evans Hall

Course control number 54284
Current enrollment information

Professor Kenneth A. Ribet
Telephone: (510) 642-0648
Fax: (510) 642-8204
Office hours (885 Evans Hall)
photo of Enigma rotors


Math 55 is the official prerequisite. However, the essential mathematical content of this course overlaps significantly with the three courses Math 110, Math 113 and Math 115. Experience with these courses is helpful, though not necessary.

The exercises in this course involve calculations that cannot be performed by hand. At the beginning of the course, all that is needed is a calculator. By the end, you will need to use Sage or Magma to do the homework. Since Sage is free, while Magma is a commercial product, I urge you to download Sage and try it out as soon as possible. You can also work with Sage online instead of downloading it and using it locally.


An introduction to mathematical cryptography by Hoffstein, Pipher and Silverman.

Although this book describes itself as "self-contained," it includes compact summaries of material from and abstract and linear algebra and from number theory. If you haven't had courses in these subjects, be prepared for moments when you will need to digest a lot of material in a short amount of time. As we go through the course, check ahead for problematic passages.

Be sure to consult the authors' errata list if you think that you've spotted an error. The authors will be grateful to readers like us if we send them additional corrections.

The book is available for purchase directly from Springer or from Amazon. However, if you have an IP address that is associated with the campus and navigate to, you should see things like

California Digital Library Springer
BUY A (Softcover) PRINT COPY (USD $24.95). 
Further, you can download the book, chapter by chapter, as a series of eight .pdf files from the springerlink site. Accordingly, you can have the book available to you on your laptop, desktop or other digital device. If you are not physically on campus but need access to electronic resources for which UC is a subscriber, see the UC Berkeley Library Proxy Server help page for some pointers.


Please do not plan travel on these dates: The L&S student calendar lists drop and grade-change deadlines. The drop deadline is February 17, while the deadline to change grading options is March 23. If all goes well, midterms will be returned to you on February 16 and March 22.


The catalog description is very terse: "Construction and analysis of simple cryptosystems, public key cryptography, RSA, signature schemes, key distribution, hash functions, elliptic curves, and applications." The book covers these topics and more. I plan to follow the textbook for the most part but will base a few lectures on other documents.

As I stress above, the book can be viewed as self-contained only because it includes quick summaries of a number of topics that are best viewed as inputs to a study of cryptography. Among these topics are

You can do yourself a big favor by checking out these sections (§§1.2-1.4, §2.5, §2.10, §3.1, §3.9, §§5.1-5.2) ahead of time to see whether they are likely to be difficult or easy for you. I will of course discuss them in class, but my treatment will be a bit fast for people who have never thought about the relevant subjects in their lives.

Recommended reading and other links

Some of these are left over from the 2010 list. I added additional links during the course and will continue as appropriate.


You may find the authors' Snippets from Selected Exercises helpful if you want to paste strings into a computer application.
  1. Assignment due January 26, 2012
  2. Assignment due February 2, 2012
  3. Assignment due February 9, 2012: Problems 2.34, 2.35, 2.36, 2.37, 2.38 (primitive root = multiplicative generator), 2.39. Also: Let K and F be the fields of order 73 defined respectively by the cubic polynomials x^3 + 6x^2 + 5x + 3 and x^3 + 2x^2 + 3. Find an explicit isomorphism of fields from K to F.
  4. Assignment due February 16, 2012: write out complete bulletproof solutions to the six exam questions. For computations, it's OK to use sage. Also, answer this supplemental question: Suppose you know that Alice and Bob have published RSA moduli that share a prime factor. How can you factor the two moduli? (Although this assignment is due at 9:40AM on Thursday, I will accept homework papers until 5PM on Friday. To hand in an assignment once class ends on Thursday, you can slide your paper under my door (885 Evans Hall).)
  5. Assignment due February 23, 2012: Problems 2.23(c,d), 3.1 (b,e), 3.5, 3.6, 3.8(d), 3.9(a,b), 3.10, 3.12, 3.13(b, part iv), 3.14(g), 3.16 (but use prime_pi of sage instead of writing your own program).
  6. Assignment due March 1, 2012: Problems 3.18, 3.19, 3.21c, 3.23d, 3.24c, 3.25d, 3.26e, 3.28. Feel free to use sage on these problems as appropriate.
  7. Assignment due March 8, 2012: Problems 3.31, 3.32, 3.34 (make sage do the work!), 3.38, 3.39, 3.41, 3.42.
  8. Assignment due March 15, 2012: Problems 5.1, 5.2, 5.3, 5.4cd, 5.5de, 5.6a. In all cases, use sage as much as possible. You might want to look at my notebook on elliptic curves over finite fields and Jared Weinstein's notebook on elliptic curves over the rational field.
  9. Assignment due March 22, 2012: write out complete bulletproof solutions to the exam questions. For computations, it's OK to use sage. (Although this assignment is due at 9:40AM on Thursday, I will accept homework papers until 5PM on Friday. To hand in an assignment once class ends on Thursday, you can slide your paper under my door (885 Evans Hall).)
  10. Assignment due April 5, 2012: 5.7d, 5.10d (use the algorithm but let sage do the intermediate computations), 5.13, 2.10, 5.14, 5.18cd, 5.20 (using sage), 5.22abc
  11. Assignment due April 12, 2012: Carry out the computations of problem 5.30 using weil_pairing of sage. Do problems 5.34 and 5.35, referring to the book's description of a distortion map for the latter problem. Continue with problems 5.37, 5.38, 5.39, 5.40, 5.41. We are ahead of the lectures here, so you'll need to look at sections 5.8 and 5.9.
  12. Assignment due April 19, 2012: Problems 5.42 and 5.43; problems 4.4, 4.21, 4.22, 4.24, 4.25, 4.27, 4.28, 4.29.
  13. Assignment due April 26, 2012: Problems 4.33, 4.34, 4.35, 4.36, 4.38, 4.39 (using sage), 4.41 (a calculus problem!), 4.46.


Course grades will be based on a composite numerical score that is intended to weight the course components roughly as follows: midterm exams 15% each, homework 25%, final exam 45%.

I have taught this course twice before.

You might want to read the student evaluations for this course.

	HTML 4.01!

Last Updated: