M 343 L Applied Number Theory Fall 07


INSTRUCTOR: Felipe Voloch (RLM 9.122, ph.471-2674, )

CLASS HOURS: Tue-Thu 9:30 -- 11:00 RLM 5.126.


OFFICE HOURS: Wed 9:00 -- 11:00 or by appointment.

TEXTBOOK: W. Trappe and L. C. Washington, Introduction to Cryptography with Coding Theory, 2nd edition. There is an errata on the webpage.

NOTE ON PREREQUISITES: In the past, the university's course schedule has listed the prerequisites for this class as being 343K and 328K. This is incorrect. It should have said 343K or 328K, but anyhow the prerequisites are flexible. If you are not sure whether you have the right prerequisites, please contact me.

EXAMS AND GRADE POLICY: The grade will be determined from homework, a midterm and a final. The two best grades from among these three will count 50% each for the course grade. The midterm will be on Thursday, November 8th during class time and the final on Thursday, December, 13th, 2 to 5PM in RLM 5.114. Makeups will not be given.

HOMEWORK: The homework will have two parts. One part, worth 40% of the homework grade will consist of problems that will be assigned periodically in class and will be due a week after they are assigned. The other part, worth 60% of the homework grade, will consist of a computer project. The computer project will be assigned in October.

COURSE DESCRIPTION:The purpose of this course is to introduce students to applications of Number Theory to Cryptography. This topic addresses the problem of preserving data integrity during transmission or storage against malicious attacks. Security on the Internet is a hot topic and it is all based on interesting mathematics. The prerequisites will be kept to a minimum, but previous exposure to elementary number theory or algebraic structures would be helpful.

Topics to be covered:

Basic properties of integers. Prime numbers and unique factorization. Congruences, Theorems of Fermat and Euler, primitive roots.

Primality testing and factorization methods.

Cryptography, basic notions. Public key cryptosystems. RSA. Implementation and attacks.

Discrete log cryptosystems. Diffie-Hellman and the Digital Signature Standard. Elliptic curve cryptosystems.

Symmetric cryptosystems, such as DES and AES.


There will be a review class for the midterm on Thursday, November 1st. There will be no class on Tuesday, November 6th and the midterm itself is on Thursday, November 8th.


  1. Chapter 2, problems 2, 3, 5, 6, 18. Due 9/13.
  2. Chapter 3, problems 1, 4, 5, 12, 23. Due 9/20.
  3. Chapter 3, problems 16, 22 and Chapter 6, problems 2, 3, 7. Due 9/27.
  4. Chapter 7, section 7.6, problems 1, 2, 7, 10 and 11. Due 11/15.

Computer project

  1. Chapter 6 (Section 6.9) Problems 5, 6, 10, 12, 13. Due 10/25.
  2. Chapter 7 (Section 7.7) Problems 1, 2, 3 and Chapter 16 (Section 16.8), Problems 1 and 2. Due 11/27.

Some links:

  1. PARI/GP homepage.
  2. AKS
  3. Lesson in PARI/GP and another file with some more examples.
  4. Another lesson in PARI/GP and Pollard's p-1 algorithm.
  5. Elliptic curve applet.
  6. Schneier's article.
  7. Elliptic curve lesson in PARI/GP.
  8. Elliptic curves on the Wii.
  9. Elliptic curves on Microsoft's DRM also described in W. Stein's textbook on Number Theory.
  10. Elliptic curves on German passports.
  11. midterm.