MAT C16: Coding Theory and Cryptography
Winter Term 2012

Instructor: Leo Goldmakher

HELP BUTTON

Click here for some useful resources.

Course Information

Instructor Information

Lectures
Tuesdays 17:00 -- 18:00, IC 326
Thursdays 17:00 -- 19:00, IC 326 		Office hours
Mondays 13:00 -- 15:00, IC 346
Tuesdays 11:00 -- 12:00, IC 346
Thursdays 11:00 -- 12:00, IC 346
Textbook
W. Trappe and Lawrence Washington,
 Introduction to Cryptography with Coding Theory, 2nd edition,
 Prentice Hall, 2005. 		email
leo {dot} goldmakher {at} utoronto {dot} ca
Course Syllabus
Syllabus.pdf 		Telephone
(416) 208-5110
DATE LECTURE SUMMARY ASSIGNMENT
(to be quizzed on Thursday of the week listed) 		PROBLEM OF THE WEEK DOCUMENTS
         
Week 1: 1/9 -- 1/13 Tuesday's Lecture:
  •  
Thursday's Lecture:
  •  
     Course Syllabus
Week 2: 1/16 -- 1/20 Tuesday's Lecture:
  •  
Thursday's Lecture:
  •  
      
Week 3: 1/23 -- 1/27 Tuesday's Lecture:
  •  
Thursday's Lecture:
  •  
      
Week 4: 1/30 -- 2/3 Tuesday's Lecture:
  •  
Thursday's Lecture:
  •  
  • Describe the Euclidean algorithm, and prove that it outputs the gcd. (This will be on the quiz, along with other questions from the list below.)
  • Determine (with justification) all common factors of 1134 and 4567. Be able to do this for any two given integers.
  • Trappe-Washington section 2.13 # 1--8, 10, 12, 18, 25.
    		•    Quiz solutions
    Week 5: 2/6 -- 2/10 Tuesday's Lecture:
    •  
    Thursday's Lecture:
    •  
    		      
    Week 6: 2/13 -- 2/17 Tuesday's Lecture:
    •  
    Thursday's Lecture:
    •  
  • Come up with a pseudorandom number generator which you have never seen before. Discuss its strengths and weaknesses.
  • Trappe-Washington section 2.13 # 11, 12, 19, 20 (solve this using any method you like -- you don't need to use matrices), 22, 23, 25. Also, try out Section 2.14 # 9.
    		•    Quiz solutions
    Reading week: 2/20 -- 2/24 No classes      
    Week 7: 2/28 -- 3/2 Tuesday's Lecture:
    •  
    Thursday's Lecture:
    •  
    		      
    Week 8: 3/5 -- 3/9 Tuesday's Lecture:
    •  
    Thursday's Lecture:
    •  
    		      
    Week 9: 3/12 -- 3/16 Tuesday's Lecture:
    •  
    Thursday's Lecture:
    •  
    		      

    THURSDAY, MAR. 15

    		Midterm Exam   Midterm solutions  
    Week 10: 3/19 -- 3/23 Tuesday's Lecture:
    •  
    Thursday's Lecture:
    •  
  • Trappe-Washington section 3.13 # 7, 8, 11, 12 (hint: 101 is prime), 13, 15, and prove part (c) of 15. [Hint: consider the list of n fractions {1/n, 2/n, 3/n, ..., n/n}. Reduce all the fractions and count!]
  • Find 5-1 (mod 69), i.e. the multiplicative inverse of 5 in (Z69)x.
  • Find all values of x in Z77 satisfying x13 = 3.
    		•    Quiz solutions
    Week 11: 3/26 -- 3/30 Tuesday's Lecture:
    •  
    Thursday's Lecture:
    •  
    		      
    Week 12: 4/2 -- 4/6 Tuesday's Lecture:
    •  
    Thursday's Lecture:
    •  
    		 (1) Prove that (x + 1)n ≡ xn + 1 (mod n) if and only if n is prime.
    (2) Suppose a is relatively prime to n. Prove that (x + a)n ≡ xn + a (mod n) if and only if n is prime.
    (3) Prove that an-1 ≡ 1 (mod n) for every a in Zn if and only if n is prime.
    (4) Recall that 561 is a Carmichael number: it fools the Fermat test. Does it also fool Miller-Rabin?
    (5) Trappe-Washington section 6.8 # 3, 7, 9, 15, 16, 17, 18, 20.     		  Quiz solutions

    THURSDAY, APR. 19

    		Final Exam In my office, IC 346. Schedule:

    • 11:00 Adam
    • 11:30 Rafayel
    • 12:00 Zhuo
    • 12:30 Chaveen

    • 1:30 Meng
    • 2:00 Wen Bo
    • 2:30 Vitz
    • 3:00 Seacy
    		   Instructions