M 375 Mathematics of Information Transmission Spring 99

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

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.

Homework assignments:

I will also post Steffen Rost's solutions of the homework in pdf format. Note that they are mostly correct but not all problems are completely right. I thank Steffen for allowing me to post his solutions. They are available also from his web page.
  1. Chapter 7 problems 10,16 and 17. Due 1/28.
  2. Chapter 10: 10.2 exercises 1,2; 10.3 exercise 1; problems 2,6. Due 2/4. Steffen Rost's solutions.
  3. Chapter 10: 10.4 exercises 1,2,3,4. Due 2/11 Steffen Rost's solutions.
  4. Chapter 11: 11.2 exercises 1,2; problems 1,9,12,13. Due 2/18. Steffen Rost's solutions.
  5. Chapter 10, 10.5 exercises 1,2; Chapter 11: 11.5 exercises 1,2; problem 10. Due 2/25. Steffen Rost's solutions.
  6. Find a prime with at most ten (decimal) digits. Find an irreducible polynomial of degree at most nine with coefficients in F2. Grade will be proportional to size of answer. Due 3/4.
  7. 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.)
  8. Chapter 4: 4.1 exercise 1; 4.2 exercise 1; 4.3 exercise 2; problem 11. Due 4/8. Steffen Rost's solutions.
  9. Chapter 4: 4.4 exercises 1,2 and 3; 4.5 exercise 1. Due 4/15. Steffen Rost's solutions.
  10. Chapter 4: 4.6 exercise 1; 4.7 exercises 1 and 2. Due 4/22. Steffen Rost's solutions.
  11. Chapter 4: problems 15, 16 and 18. Due 4/29. Steffen Rost's solutions.

Info on final:

The final exam will be on Thursday, May 13th, 9-12, at WEL 2.256. Bring a calculator. The exam will cover the whole course but will emphasize the second half. There will be a review for the exam in class on Thursday, May 6th.

Some links:

 You can access Pari interactively here, for instance. Note that this page is still under development and requires netmath to be viewed in full glory. The previous link will lead you to a page from which you can download netmath as a standalone program. If you want, it is possible but not recommended, to view netmath under netscape by going here, but you'll need some plug-ins in your browser.

This page has been visited [an error occurred while processing this directive] times since May, 11th, 1997.