Week of 
Lecture 


Jan 
16 
Intro: basic definitions and examples. 
Administrativia 

23 
Divisibility, Primality, GCD 
ps1 due Jan.25;
Ch.1 Also recommended: NT1 or here 




30 
Modular arithmetics, Euclid's algorithm 
ps2
due Feb.1 Ch.2 (skip sec.2.6), 4.1 



Ch.3.1  3.3 (in sections) 
Feb 
6 
extended gcd algorithm, CRT algorithm 
ps3
due Feb.8 Ch. 3.4; 4.23 

Friday, February 16, 2007: Last Day to DROP Classes (without a 'W' grade), or to Change from Credit to Audit Status 


13 
Putting it all together: RSA (public key cryptography)  ps4 due Feb.16 (4:30pm); Ch.7.49 



20 
Another application: errorcorrecting code  Ch. 4.45 

27 
Secret sharing  ps5 due March 1 

Friday, March 9, 2007: Last Day to DROP Classes (with a 'W' grade) 





March 
6 
Midterm  March 8  ps6 due March 8 

March 


20 
Computing Square roots, Rabin encryption  Ch. 1213 

27 
Complexity of computing square roots. Applications. FiatShamir protocol.  ps7 due March 29 



April 
3 
Computing Legendre and Jacobi symbols. DiffieHellman 
ps8 due April 5 

10 
ElGamal, Discrete Log  ps9 due April 12; Ch. 11 

17 
Oneway and trapdoor functions, Schnorr ZKP  ps10 due Apr. 20 

24 
Rings  Ch. 9, ps11 due Apr. 26 



May 
1 
Polynomial rings; Summary  

Classes end on Thursday, May 3, 2007 


16 
Final:
rescheduled
Mon 
