Number Theory and Cryptography

Elena Klimenko
Office: C5 A05
Office Hour: Tuesday, 3:30-4:30 pm
Office Phone: (07071) 29-78593
Email: klimenko at hhu dot de

Announcements

• The file you are interested in is here.


• In the day of the exam: Please do not forget to bring your student ID, a pen with black or blue ink (no pencils!). You may also bring two two-sided sheets of paper (size A4) completed with your (handwritten) notes, a simple watch that doesn't have internet access, doesn't beep, and doesn't have an alarm. No calculators, no computers, no smartphones, et cetera.


• The final exam (Klausur) will be held on Friday, February 16, from 10:15-12:15 in Lecture Hall N9 (Hörsaalzentrum Morgenstelle).


• Inspection (post-exam review) will take place on Monday, February 19, 5:30 PM in Seminar Room S06 (C5H05, 5th floor).

Lecture

• Tuesday: 12:05 - 1:35 pm in Lecture Hall N8; Friday: 12:05 - 1:35 pm in Lecture Hall N14 / M1 (Building C).

Exercise class

• Wednesday: 12:05 - 1:35 pm in Lecture Hall N14 / M1 (Building C). The time is fixed now, but please check the website again before you go to the exercise class - the place can change!

Content

• RSA public key cryptosystem. Primality testing, AKS algorithm.
• Factorization algorithms, number field sieve.
• Quadratic reciprocity in cryptography.
• The discrete logarithm problem.
• Dynamical systems and Pollard's rho method.
• Elliptic curve cryptography.
• Lattices and post-quantum cryptography.
• Zero-knowledge proofs, digital signatures, and hash functions.

Prerequisites

• Linear Algebra 1-2, Analysis 1, Algebra.

Homework

• Homework will be assigned every Friday. You have one week for solving it, it is due before class on Fridays. You are encouraged to discuss homework with each other, but you must turn in your own work.

Homework 1 (due Friday, October 27th, 12:05 pm).
Homework 2 (due Friday, November 3rd, or Tuesday, November 7th, 12:05 pm).
Homework 3 (due Friday, November 10th, 12:05 pm).
Homework 4 (due Friday, November 17th, 12:05 pm).
Homework 5 (due Friday, November 24th, 12:05 pm).
Homework 6 (due Friday, December 1st, 12:05 pm).
Homework 7 (due Friday, December 8th, 12:05 pm).
Homework 8 (due Friday, December 15th, 12:05 pm).
Homework 9 (due Friday, December 22nd, 12:05 pm).
Homework 10 (due Friday, January 12th, 12:05 pm).
Homework 11 (due Friday, January 19th, 12:05 pm).
Homework 12 (due Friday, January 26th, 12:05 pm).
Homework 13 (due Friday, February 2nd, 12:05 pm).

Books

• Jeffrey Hoffstein, Jill Pipher, Joseph H. Silverman: An introduction to mathematical cryptography.
• Stefan Müller-Stach, Jens Piontkowski: Elementare und algebraische Zahlentheorie.
• Joseph H. Silverman, John Tate: Rational points on elliptic curves.
• Nigel Smart: Cryptography: An Introduction (online version: http://www.cs.bris.ac.uk/~nigel/Crypto_Book/).
• Lawrence C. Washington: Elliptic Curves: Number Theory and Cryptography.

Exam

• The final exam (Klausur) will be held on Friday, February 16, from 10:15-12:15 in Lecture Hall N9 (Hörsaalzentrum Morgenstelle).


• In the day of the exam: Please do not forget to bring your student ID, a pen with black or blue ink (no pencils!). You may also bring two two-sided sheets of paper (size A4) completed with your (handwritten) notes, a simple watch that doesn't have internet access, doesn't beep, and doesn't have an alarm. No calculators, no computers, no smartphones, et cetera.


• Inspection (post-exam review) will take place on Monday, February 19, 5:30 PM in Seminar Room S06 (C5H05, 5th floor, C-Bau).


• In order to take part in the exam, you must have correctly done at least 50% of the homework assignments and successfully present one of them in the exercise class.