CLASS HOURS: Tue, Thu 9:30 -- 11:00 RLM 5.118

UNIQUE NUMBER: 53420

OFFICE HOURS: Wed 10:00 -- 11:30 or by appointment.

TEXTBOOK: D. Welsh Codes and Cryptography.I plan to cover Chapters 3,4,7,8,10 and 11.

EXAMS AND GRADE POLICY: I plan to assign weekly homework which will count 20% of the grade. There will be a midterm on Thursday, March, 25th, which will be worth 30% of the grade and a final on Thursday, May, 13th, which will be worth 50% of the grade. Makeup for the midterm will only be given for substantiated reasons and no makeup for the final will be given.

COURSE DESCRIPTION:The purpose of this course is to introduce students to applications of Number Theory to Cryptography and Error-correcting codes. These two topics address the problem of preserving data integrity during transmission or storage. The first deals with protecting information against malicious attacks and the second against interference due to noise. 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. Introduction to finite fields. Running time of algorithms.

Cryptography, basic notions. Public key cryptosystems. RSA. Hash functions. Discrete log cryptosystems.

Error Correcting Codes, Vector spaces over finite fields, Hamming norm, coding, decoding. Examples of codes. Hamming, Golay, cyclic, BCH, Reed-Solomon, etc.

- Chapter 7 problems 10,16 and 17. Due 1/28.
- Chapter 10: 10.2 exercises 1,2; 10.3 exercise 1; problems 2,6. Due 2/4. Steffen Rost's solutions.
- Chapter 10: 10.4 exercises 1,2,3,4. Due 2/11 Steffen Rost's solutions.
- Chapter 11: 11.2 exercises 1,2; problems 1,9,12,13. Due 2/18. Steffen Rost's solutions.
- Chapter 10, 10.5 exercises 1,2; Chapter 11: 11.5 exercises 1,2; problem 10. Due 2/25. Steffen Rost's solutions.
- Find a prime with at most ten (decimal) digits. Find an irreducible
polynomial of degree at most nine with coefficients in
**F**_{2}. Grade will be proportional to size of answer. Due 3/4. - Read and write a short commentary on the article on elliptic curve cryptosystems that appeared on Wired magazine vol. 5.12. Due 3/11. (If you want practice problems, try the quizzes on Certicom's tutorial.)
- Chapter 4: 4.1 exercise 1; 4.2 exercise 1; 4.3 exercise 2; problem 11. Due 4/8. Steffen Rost's solutions.
- Chapter 4: 4.4 exercises 1,2 and 3; 4.5 exercise 1. Due 4/15. Steffen Rost's solutions.
- Chapter 4: 4.6 exercise 1; 4.7 exercises 1 and 2. Due 4/22. Steffen Rost's solutions.
- Chapter 4: problems 15, 16 and 18. Due 4/29. Steffen Rost's solutions.

Some links:

- Report of a factoring breakthrough from the NYTimes. And some more information from RSA.
- Class newsgroup.
- Web page of a course on error correcting codes from Stanford.
- A simplified DES algorithm(pdf file) by E. Schaefer.
- The Error Correcting Codes (ECC) Home Page
- RSA Laboratories
- Certicom and their elliptic curves tutorial.
- Richard Pinch: Cryptography page
- Pari.

This page has been visited times since May, 11th, 1997.