Math 458 SPRING 2015, List of lectures
On this page I will post content of all lectures. All handouts also will be posted here.
Monday, March 30: Simple substitution ciphers. Idea of asymmetric cryptography.
Divisibility. Sections 1.1-1.2, 1.7.
Reading assignment: Read Section 1.1.1.
Wednesday, April 1: Euclidean algorithm. Section 1.2.
Please find your homework!
Friday, April 3: More on Euclidean algorithm. Congruences. Sections 1.2-1.3.
Monday, April 6: Modular arithmetic. Section 1.3.
Wednesday, April 8: Fast powering. Prime numbers and unique factorization.
Friday, April 10: Fermat little theorem. Primitive roots. Section 1.5.
Monday, April 13: Symmetric ciphers and public key cryptography. Sections 1.7 and 2.1.
Reading assignment: Read Section 1.6.
Wednesday, April 15: The discrete logarithm problem and its applications.
Friday, April 17: How to solve DLP. Sections 2.6-2.7.
Monday, April 20: The Chinese Remainder Theorem. Section 2.8.
Wednesday, April 22: The Pohlig-Hellman algorithm.
Sections 2.9. Please find solutions to theoretical problems
in Homework 2.
Friday, April 24: MIDTERM.
Here are the solutions.
Monday, April 27: More on Pohlig-Hellman algorithm. Roots of high degree.
Sections 2.9, 3.1. New homework!
Wednesday, April 29: RSA cryptosystem. Section 3.2.
Reading assignment: Read Section 3.3.
Friday, May 1: Primality testing. Section 3.4.
Monday, May 4: Factorization: Pollard p-1 algorithm.
Section 3.5. New homework!
Wednesday, May 6: Towards quadratic sieve. Section 3.6.
Friday, May 8: Quadratic sieve. Section 3.7.
Monday, May 11: Discrete log again: index calculus.
Section 3.8. New homework!
Wednesday, May 13: Quadratic residues and nonresidues. Section 3.9.
Friday, May 15: Goldwasser-Micali cryptosystem. Section 3.10.
We will have MIDTERM next Friday. Please find here
Monday, May 18: Rings, fields, and polynomials.
Section 2.10. New homework!
Wednesday, May 20: Midterm review.
Friday, May 22: MIDTERM.
Here are the solutions.
Monday, May 25: Memorial Day, no classes.
Wednesday, May 27: Construction of finite fields. Section 2.10.
Friday, May 29: Elliptic curves. Section 6.1.
Monday, May 25: Elliptic curves over finite fields. Section 6.2.
Wednesday, May 27: Cryptography with elliptic curves. Sections 6.3-6.4.
Please find here review problems for the final.
Friday, May 29: Factorization with elliptic curves. Section 6.6.
Here are the answers and solutions to review problems.