Math 110 Spring 2013
Applied Number Theory and Field Theory

Lectures: TuTh 2:15PM - 3:30PM, No more lectures this quarter.

Instructor: Peter McNamara, 380-382H, Email:

Office Hours: by email

Course Assistant: Elizabeth Goodman, 380-380L, Email:

Office Hours:Tu 1:15-2:15, 3:45-4:45, W 10-12. In 380-L.

Textbook: Trappe and Washington - Introduction to Cryptography with Coding Theory.

WIM: The Writing in the Major assignment is to produce a short essay on the topic of the Pollard rho algorithm.

You can find discussions of the Pollard Rho algorithm in each of the following books:

  • [CLRS] Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L. & Stein, Clifford - Introduction to Algorithms
  • [G] Garrett - Making, Breaking Codes: An Introduction to Cryptography.
  • [K] Koblitz - A Course in Number Theory and Cryptography.
  • The main point of this project is to concentrate on the exposition. Your paper should be 4-7 pages long and typed. The dominant typesetting system (and with good reason) in mathematics is LATEX, which is recommended.

    Important dates: Thu May 16, typed draft due (can be handed in earlier for feedback, allow one week for a response), Tue May 21, drafts returned, Thu May 30, Final papers due.

    Problem Sets: Due Thursdays, in class. There will be no late homeworks accepted (this is as much a consideration to the grader as anything else), and the each student will have their lowest homework score dropped.
    Homework 1 Due April 11. Solutions
    Homework 2 Due April 18. Solutions
    Homework 3 Due April 25.Solutions
    Homework 4 Due May 2. Solutions
    No homework due the week of May 9 due to midterm.
    Week of May 16: Write your WIM drafts.
    Homework 5 Due May 23. Solutions

    Grading: Homework 20%, Writing in Major 15%, Midterm 20%, Final Exam 45%.

    Exams: There will be one midterm and one final exam. The midterm exam will be Tuesday 7 May, in class. The times for the final exam set by the university.

    Midterm The midterm begins at 2:15pm sharp, and lasts for 75 minutes. Students will be allowed to take in two pages of double sided notes, of letter or A4 size. The midterm will cover all topics covered in class or in the homeworks. This includes elementary number theory (TW 3.1-3.7,3.12), RSA (6.1), Primality testing (eg Miller-Rabin, 6.3), Discrete Logarithms (Ch 7) and Error Correcting Codes (Ch 18).
    Midterm Solutions

    Final Exam The final exam is at 7pm, on Tue 11 June, in 380-380F (check this against the official timetable). It lasts three hours. Students will be allowed to take in two pages of double sided notes, of letter or A4 size. The final exam will cover all topics covered in class, the homeworks or the WIM. In addition to the midterm topics, this includes TW 3.9,3.10 (square roots modulo n, Legendre and Jacobi symbols), Factoring algorithms (continued fraction based on x^2=y^2 mod n, Pollard rho, p-1, Elliptic Curve), Elliptic Curves (TW 16.1-16.3), Discrete Fourier Transform.
    Here are some practice problems. The main subject covered that is missing in this compilation is elliptic curves, for which Trappe and Washinton's problems are of a suitable level.