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, look ahead so that you can get a head start on 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);
• Next midterm exam, March 20, 2012 in class (Questions and skeletal solutions from 2009 and the analogue from 2010);
• Final Exam, Wednesday May 9, 2012 11:30AM-2:30PM (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

• 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!
• The Brown Math Department's Mathematical Cryptography Calculator
• 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.

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.

Last Updated: