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 email: Telephone: (510) 642-0648 Fax: (510) 642-8204 Office hours (885 Evans Hall)

Prerequisites

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.

Textbook

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 http://www.springerlink.com/content/978-0-387-77993-5, you should see things like

California Digital Library Springer

BUY A (Softcover) PRINT COPY (USD $24.95). 

Examinations

• First midterm exam, Valentine's Day in class (Questions and skeletal solutions from 2009 and the analogue from 2010 year's class); maximum possible score = 40, mean = 30.6, standard deviation = 6.6. There are now questions and skeletal solutions for February's exam.
• Next midterm exam, March 20, 2012 in class (Questions and skeletal solutions from 2009 and the analogue from 2010); maximum possible score = 35, mean = 22.2, standard deviation = 6.2. There are now questions and skeletal solutions for the second midterm exam.
• Final Exam, Wednesday May 9, 2012 11:30AM-2:30PM in 9 Evans; maximum possible score = 50, mean = 34.47, standard deviation = 9.53. (Questions and possible solutions from 2009 and the analogue from 2010 year's class.)

Lectures

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

• Basic linear algebra as in Math 54 and Math 110;
• Elementary number theory as presented in Math 55 and Math 115;
• Not-so-elementary number theory (quadratic residues, quadratic reciprocity), which is usually discussed in Math 115;
• Group theory as studied in Math 113;
• Commutative ring theory (including ideals and quotient rings) as studied in Math 113;
• The basic theory of elliptic curves (not typically studied in our undergraduate courses).

Recommended reading and other links

• Mining your Ps and Qs by Nadia Heninger et. al.
• Factoring integers using elliptic curves over Q by X. Li and J. Zeng (July, 2012).
• What on earth is `index calculus'? by Claus Diem.
• Thinking, fast and slow by Daniel Kahneman. This book teaches us that we are not wired for probability. Even professionals and other experts make gross errors in estimating probabilities, especially conditional probabilities.
• Chances are, NY Times blog by Steven Strogatz about conditional probability.
• The 16th workshop on Elliptic Curve Cryptography, ECC 2012
• Heuristics on pairing-friendly elliptic curves by John Boxall.
• A one round protocol for tripartite Diffie-Hellman by Antoine Joux
• The Cunningham project.
• The development of the number field sieve:
  • The number field sieve by A. K. Lenstra, H. W. Lenstra, Jr., M. S. Manasse, J. M. Pollard.
  • Factoring integers with the number field sieve by J. P. Buhler, H. W. Lenstra, Jr., Carl Pomerance
• Integer Factoring by Arjen K. Lenstra (may require UC Berkeley credentials).
• Wikipedia's page on L-notation.
• Gary L. Miller's article Riemann's hypothesis and tests for primality. This is reference [78] in our textbook.
• Sage for Power Users by William Stein.
• An amazing research article about RSA key generation in the wild; you might start by reading the NY Times's account of the findings.
• A blog post by Nadia Heninger reassuring us that RSA keys for serious web sites are much more secure than the New York Times suggested.
• Cover and Decomposition Index Calculus on Elliptic Curves made practical.
• Civil War Diary Code: break this code and you'll make the UC Berkeley history department very happy!
• SAGE download
• Introduction to Cryptography by Johannes Buchmann
• Cryptography: theory and practice by Doug Stinson
• Making, Breaking Codes: introduction to cryptology by Paul Garrett
• Introduction to Cryptography with Coding Theory by Wade Trappe and Lawrence C. Washington
• Elliptic curve cryptography: The serpentine course of a paradigm shift by Ann Hibner Koblitz, Neal Koblitz and Alfred Menezes
• Primality Testing in Polynomial Time by Martin Dietzfelbinger (reference [34] in our book)
• John M. Pollard's home page
• Smooth numbers and the quadratic sieve, a talk by Carl Pomerance
• Table of the smallest Carmichael numbers with a given number of prime factors from the On-Line Encyclopedia of Integer Sequences
• Poker hand frequences, prepared for my Fall, 1997 Math 55 class by GSI Loren Looger; note that the number of hands having three of a kind is 54912, rather than the 54972 that's indicated!
• The Hot Hand in Basketball by Gilovich, Vallone and Tversky
• The no-stats all-star by Michael Lewis
• CAN YOU CRACK A CODE? Try Your Hand at Cryptanalysis from our friends at the FBI.
• Simon Singh's The Code Book
• A cipher to Thomas Jefferson by Lawren Smithline (requires a subscription to American Scientist, but UCB is an institutional subscriber)
• A new approach to generating random numbers
• The March 2010 issue of the Notices of the American Mathematical Society is devoted to cryptography.
• A tale of two sieves by Carl Pomerance
• Cryptography by David R. Kohel
• Exploring Cryptography Using the Sage Computer Algebra System, honors thesis by Minh Van Nguyen
• Nova: the Spy Factory

Homework

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 7³ 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.

Grading

I have taught this course twice before.

• In 2009, there were 29 students who took the final exam. Letter grades were distributed as follows: 11 As, 15 Bs, 3 Cs.
• In 2010, I had 35 students. There were 14 As, 17 Bs, 3 Cs and 1 F.
• In this class, 32 students took the final exam. They received 10 A's, 17 B's and 5 C's.

Last Updated: