Two exam review sessions will be scheduled

before exams to compensate for the skipped lectures Jan 6,8.

**Week 1. Jan 11,13,15**

Review of algebra, Euclidean algorithm, modular arithmetic,

prime numbers, factorization, finite fields

IMC, Sections 1.1-1.4.

**Week 2. Jan 20,22**

From algebra to cryptosystems, algorithms for finite fields, powers by squaring, primitive roots,

historical introduction to early cryptosystems, symmetric and asymmetric ciphers

IMC, Sections 1.5-1.7

**Week 3. Jan 25,27,29**

Diffie-Hellman, the birth of public key cryptography, discrete logarithms, El Gamal cipher

IMC, Sections 2.1-2.4

**Week 4. Feb 1,3,5**

Basic computational complexity, counting bit operations, polynomial time algorithms, Fermat’s little theorem and Euler’s formula, the RSA cryptosystem,

IMC, Sections 2.6, 3.1, 3.2,

**Week 5. Feb 8,10,12**

Complexity of the discrete log problem, survey lecture on quantum computing and future implications, RSA attacks and countermeasures, primality testing

IMC, Sections 3.3-3.4, 5.7, 8.11

**Week 6. Feb 15,17,19**

Integer factorization, Pollard’s p-1 algorithm, factorization by differences of squares, cryptographic applications,

quadratic reciprocity and Goldwasser-Macali cryptosystem (optional)

IMC, Sections 3.5, 3.6, (3.9)

**Week 7. Feb 22,24,26**

digital signatures, RSA signatures

IMC, Sections 4.1, 4.2, 4.3

** midterm exam **

**Week 8. Mar 0,2,4**

Basic probability, review of counting problems, Bayes’s theorem

IMC, Sections 5.1-5.3

**Week 9. Mar 14,16,18**

Information theory, basic definitions from Shannon, entropy with examples, applications to one-time pads, perfect secrecy, and password entropy

IMC, Section 5.6

**Week 10. Mar 21,23,25**

elliptic curves, curves over finite fields, addition law, EC discrete logs

IMC, Sections 6.1, 6.2, 6.3

**Week 11. Mar 28,30,32**

more elliptic curve cryptography, Lenstra’s elliptic curve factorization algorithm

IMC, Sections 6.4, 6.5, 6.6

**Week 12. Apr 4,6,8**

Hash functions, pseudorandomness, bitcoin

IMC, Sections 8.1, 8.2, 8.8

**Week 13. Apr 11,13,15**

Zero Knowledge Proofs, further applications to cryptography

IMC, Sections 8.3, 8.4

**Week 14 Apr 18,20,22**

more applications of cryptography as time permits such as obfuscation, homomorphic encryption,

IMC, Section 8.9

review

Final: Wednesday April 27, 2016, 2:00-3:50pm.