Math 158: Cryptography (Fall 2016)

This course concerns the mathematical problems underlying public-key ciphers and digital signatures, as well as algorithms to solve them. Topics include discrete logarithms, integer factorization, elliptic curves, and lattices. These topics provide an appealing introduction to several topics in number theory, abstract algebra, and algorithms.

Announcements

  • (12/23) Some exam statistics (out of 75 points): the mean was 55.9, the median was 56.5, and the standard deviation was 9.3. Thanks for a great semester, and enjoy your break!
  • (11/6) I am moving this week’s office hours to Monday 3-4 and Tuesday 12-1:30, in light of the exam on Wednesday.
  • (11/6) The midterm on Wednesday will focus on material not covered on the first midterm, through Chapter 4 (nothing about elliptic curves). The relevant textbook sections are 2.7-9, 3.1-5, and 4.1-3. No questions will be exclusively about material covered on the first exam, but it may come up in a tangential way. Remember to make a one page note sheet (front and back). I will provide tables 2.2, 2.3, 3.1, 4.1, 4.2, and 4.3 from the textbook in the exam packet.
  • (10/2) I am moving this week’s office hours to Monday 4-5 and Tuesday 12-1:30, in light of the exam on Wednesday.
  • (10/2) The midterm on Wednesday will cover material from the first three problem sets, textbook sections 1.2-1.5 and 2.2-2.6, and anything discussed in lecture up to the first half of Friday’s class (not including the BSGS algorithm). Remember to make a one page note sheet (front and back). I will provide tables 2.2 and 2.3 in the exam packet.
  • (9/22) Brown has reassigned our classroom to Wilson 309.
  • (9/12) The problem sets will now have a hard deadline of 4am on Friday mornings, which I will refer to as “Thursday night.” This is to avoid down-to-the-wire stress about the due time.
  • (9/8) I have made a small revision to the syllabus: written problems will actually be submitted electronically using a system called Gradescope. See the submission instructions under “Problem Sets” for details.

Textbook and readings

  • The course text is An Introduction to Mathematical Cryptography, Second Edition by Hoffstein, Pipher, and Silverman. The link above will allow you to download the entire book in pdf for free (you must log in with your Brown credentials), and also to buy a discount paperback copy.
  • Python crash course covering many of the basic keywords and syntax to get started with the programming assignments.
  • Python for Non-Programmers contains a number of useful resources and links.
  • Learn Python the Hard Way is a (despite the title) very well-suited to beginners and is quite comprehensive. For our purposes, I suggest focusing on the exercises 0-4, 11, 18, 19, 21, and 29-33 (but read and consider the author’s warning at the end of exercise 0).
  • repl.it is a convenient website to code in Python (and other languages) straight through a web browser, with no installation needed.

Problem sets

Problem sets will be posetd here. Solutions will be posted after the due date. Please carefully read the submission instructions before completing the first problem set. If I say that a problem set is on the “night of Thursday,” this means that the hard deadline is 4am on the following Friday morning.

  • Submission instructions for all problem sets.
  • Problem Set 1 (due night of Thursday 9/15). Reading: sections 1.1 and 1.2.
  • Problem Set 2 (due night of Thursday 9/22). Reading: sections 1.3, 1.4, 1.5, 2.2, 2.3.
  • Problem Set 3 (due night of Thursday 9/29). Reading: sections 2.4, 2.5.
  • Problem Set 4 (due night of Thursday 10/13). Reading: sections 2.6, 2.7, 2.8.
  • Problem Set 5 (due night of Thursday 10/20). Reading: sections 2.9, 3.1, 3.2, 3.3.
  • Problem Set 6 (due night of Thursday 10/27). Reading: sections 3.4, 3.5.
  • Problem Set 7 (due night of Thursday 11/3). Reading: sections 4.1,4.2,4.3.
  • Problem Set 8 (due night of Thursday 11/17). Reading: sections 6.1, 6.2, 6.3.
  • Problem Set 9 (due night of Monday 11/28). Reading: sections 6.4, 6.5.
  • Problem Set 10 (due night of Monday 12/5). Reading: sections 2.10.1, 2.10.2, 2.10.3, 7.1.
  • Problem Set 11 (due night of Sunday 12/11). Reading: sections 7.9, 7.10.1, 7.13.1.

Exams

Exams and solutions will be posted here after they are given.

  • Midterm 1: Wednesday, October 5 in class.
  • Midterm 2: Wednesday, November 9 in class.
  • Final exam: Tuesday, December 20, 9am to noon in Foxboro auditorium.