CS982-O: Computational Number Theory for Cryptographers
Credits: 3-0-0-9
Instructor:
Dr. Nitin Saxena / Dr. Manindra Agrawal
· Major, Measurable Learning Objectives
Having successfully completed this course, the student will be able to:
· Learn how to design algorithms that require algebra
· Use libraries to do fast computations with integers, polynomials, and matrices
· Learn how error-correcting codes work
· Learn how certain cryptographic primitives are designed and how they are broken
· Prerequisites and Co-requisites
ESC 101, ESO 207, (mathematical maturity with interest in algebra)
· Texts and Special Teaching Aids
Course notes, lecture slides, and other documentations will be provided to students by
the instructor. Self-study would be an important component of this course. Useful video tutorials will also be provided to students for self-learning. Programming will not be done formally, but students are encouraged to familiarize themselves with the existing implementations.
BOOKS, LECTURES
Book, A Computational Introduction to Number Theory and Algebra, Victor Shoup.
Book, Algorithmic Number Theory (Lattices, Number Fields, Curves and Cryptography), Edited by Joseph P. Buhler and Peter Stevenhagen.
Book, Modern Computer Algebra, von zur Gathen & Gerhard.
Book, Algorithmic Number Theory, Bach & Shallit.
Book, Finite Fields, Lidl & Niederreiter.
Course, Algebra and Computation, Madhu Sudan.
Course, Computational Number Theory and Algebra, Manindra Agrawal.
· Syllabus
The students will be exposed to the following topics, roughly in this order of 12 weeks:
1. Outline. Notation. Background.
2. GCD. Chinese remaindering. Fast polynomial multiplication.
3. Fast integer multiplication. Fast integer division. Fast gcd.
4. Fast matrix multiplication. Tensor rank.
5. Factorization over finite fields.
6. Berlekamp, Cantor-Zassenhaus factoring algorithms.
7. Reed-Solomon code. List decoding. Bivariate polynomial factoring.
8. Kaltofen's blackbox multivariate factoring.
9. Integral polynomial factoring. LLL algo. Shortest vector in lattice.
10. Lattice-based cryptography: eg. NTRU Cryptosystem.
11. Primality testing. RSA cryptosystem. Diffie-Hellman. Discrete Log.
12. Integer factoring. Pollard, Fermat, Morrison-Brillhart, Quadratic sieve methods. Breaking RSA?
13. Elliptic curves and the cryptography based on it (if time permits)
The course will consist of 3 hours of lectures per week, homework, and an optional project.
· Grading
Semester grades will be based on the following weights.
- Exercises 40%
- Midterm Exam 30%
- Final Exam 30%
Semester grades will be determined after all work is completed and graded. Point ranges for letter grades will be based on several factors, including absolute and relative performance. Letter grades will not be based on a fixed, predetermined curve or point range.
Coverage of Topics
|
Topics |
Lectures |
|
1. Outline. Notation. Background. |
2 |
|
2. GCD. Chinese remaindering. Fast polynomial multiplication. |
4 |
|
3. Fast integer multiplication. Fast integer division. Fast gcd. |
3 |
|
4. Fast matrix multiplication. Tensor rank. |
1 |
|
5. Factorization over finite fields. |
3 |
|
6. Berlekamp, Cantor-Zassenhaus factoring algorithms. |
3 |
|
7. Reed-Solomon code. List decoding. Bivariate polynomial factoring. |
3 |
|
8. Kaltofen's blackbox multivariate factoring. |
6 |
|
9. Integral polynomial factoring. LLL algo. Shortest vector in lattice. |
4 |
|
10. Lattice-based cryptography: eg. NTRU Cryptosystem. |
1 |
|
11. Primality testing. RSA cryptosystem. Diffie-Hellman. Discrete Log. |
5 |
|
12. Integer factoring. Pollard, Fermat, Morrison-Brillhart, Quadratic sieve methods. Breaking RSA? |
3 |
|
13. Elliptic curves and the cryptography based on it (if time permits) |
2 |
|
Total |
40 Lectures (50 minutes each – else 27 Lectures of 75 minutes) |
Assignments/ Projects:
HomeWorks (all weeks)
Four Assignments, equally spaced, covering the topics covered.
Project Plan
Students are encouraged to read advanced research papers and give a 30mins presentation; focusing on the main ideas.