Number Theory and Cryptography - Math UN3020.
Spring 2023.
Columbia University.
Classroom: Room 312 Mathematics.
Mo, We 10:10am-11:25am.
Name: Daniele Alessandrini.
Contact: daniele.alessandrini@gmail.com.
Office: 624 Mathematics.
Office hours: Tentative schedule: Mo 2pm-3pm in Room 528 Mathematics, We 11:30am-12:30pm in Room 622 Mathematics.
The Help Room is a place for students to seek assistance with material that comes up in the course. The room is staffed by graduate students and undergraduate teaching assistants. The relevant Help Room for this course is at 406 Mathematics. You can go to the Help Room at any time when it is open, see here for the schedule.
The TAs grade the assignments and can answer questions from students. You can ask them questions by email, and they serve in the Help Room at 406 Mathematics, where you can meet them to ask your questions. You can find their email addresses on Courseworks at the Syllabus page.
| Name | Help Room Schedule |
|---|---|
| Haodong Yao | Tue 4-7pm (On Feb 7, 9am-12pm via Zoom) |
| Fan Zhou | Mon 2-4pm, Thu 1-2pm |
| Xinyi Li | Tue, Wed 1-2pm |
| Yunpeng Liu | Mon 1-2pm, Wed 4-5pm |
The Syllabus for this course.
There is no required text. We will mainly follow the notes by Gordan Savin: Numbers, Groups and Cryptography. They are available online.
This is a course in elementary number theory. We will present some applications to cryptography to motivate the theory. Main topics: Prime numbers and factorization, congruences and modular arithmetic, primitive roots, quadratic residues and quadratic reciprocity. Planned applications to cryptography include RSA encryption algorithm, Diffie-Hellmann key exchange, Miller-Rabin primality test.
| Date | No | Topic | Textbook Reference |
|---|---|---|---|
| 23/01/18 | 01 | Introduction. Numbers, operations, divisibility. | n/a |
| 23/01/23 | 02 | Divisibility. Proofs. Proofs by contradiction. Euclidean division. | n/a |
| 23/01/25 | 03 | Greatest common divisor, Euclidean algorithm. Bézout's Identity, Euclid's Lemma. | Sec. 1.1. |
| 22/01/30 | 04 | Mathematical Induction. Diophantine Equations. | Sec. 1.2. |
| 23/02/01 | 05 | Diophantine Equations. Prime numbers. | Sec. 1.2, 1.3. |
| 23/02/06 | 06 | Prime factorization. Infinitude of primes. Fermat's algorithm. | Sec. 1.3. Sec 4.1. |
| 23/02/08 | 07 | Efficiency of algorithms. Groups, rings and fields. Congruence relation. | Section 2.1, 3.1. |
| 23/02/13 | 08 | Modular arithmetic. Invertibility modulo n. | Section 2.2, 2.3. |
| 23/02/15 | Midterm 1 | ||
| 23/02/20 | 09 | Cancellation law, Zero-divisors. Linear Congruences. | Section 2.3. |
| 23/02/22 | 10 | Chinese Remainder Theorem. | Section 2.5. |
| 23/02/27 | 11 | Systems of linear congruences. Secret Sharing. Polynomials. | Section 2.5. |
| 23/03/01 | 12 | Polynomial Division. Roots. | |
| 23/03/06 | 13 | Totient Function. | Section 2.5 |
| 23/03/08 | 14 | A property of the totient function. Order of an element. Lagrange's Theorem. Euler's Theorem. | Section 5.2. Section 2.4 |
| 23/03/13 | Spring Break. | ||
| 23/03/15 | Spring Break. | ||
| 23/03/20 | 15 | Binomial Congruences. Primitive elements. | Section 5.1, 5.3. |
| 23/03/22 | 16 | Discrete Logarithm. | Section 5.4. |
| 23/03/27 | 17 | Baby-steps-giant-steps. Existence of primitive elements. | |
| 23/03/29 | Midterm 2 | ||
| 22/04/03 | 18 | Existence of primitive elements. Quadratic residues. | Section 5.3. Section 6.1. |
| 22/04/05 | 19 | Quadratic residues. Lagrange and Jacobi symbols. | Section 6.1, 6.4. |
| 22/04/10 | 20 | Quadratic reciprocity. Pseudo-random number generators. | Section 6.4. |
| 22/04/12 | 21 | Pseudo-random number generators. Miller-Rabin Test. | Section 11.1. |
| 22/04/17 | 22 | Random Primes. Classical and Modern Cryptography. | |
| 22/04/19 | 23 | RSA algorithm. Diffie-Helman key exchange. | Section 10.2. |
| 22/04/24 | 24 | Diffie Hellmann and ElGamal algorithms. Goldwasser-Micali Cryptosystem. | Section 10.1 and 10.3. |
| 22/04/26 | 25 | Shor's algorithm. Post-Quantum Cryptography. | |
| 22/05/01 | 26 | Review. |
One year of Calculus; you will also need some familiarity with proofs or a willingness to learn.
The homework will be published online in form of homework sheets every Wednesday night. You have 6 days time to submit the written solutions.
| Date | Number | Topic | Submit by | Grader |
|---|---|---|---|---|
| 23/01/18 | 01 | Numbers | 23/01/24 | Haodong and Fan |
| 23/01/25 | 02 | Euclidean algorithm | 23/01/31 | Xinyi |
| 23/02/01 | 03 | Primes | 23/02/07 | Xinyi |
| 23/02/08 | 04 | Factorization | 23/02/14 | Yunpeng |
| 23/02/15 | 05 | Modular Arithmetic | 23/02/21 | Haodong |
| 23/02/22 | 06 | Linear Congruences | 23/02/28 | Haodong |
| 23/03/01 | 07 | Polynomial division | 23/03/07 | Haodong |
| 23/03/08 | 08 | Lagrange's Theorem | 23/03/21 | Fan |
| 23/03/22 | 09 | Binomial congruences | 23/03/28 | Yunpeng |
| 23/03/29 | 10 | Discrete Logarithm | 23/04/04 | Fan |
| 23/04/05 | 11 | Quadratic Residues | 23/04/11 | Xinyi |
| 23/04/12 | 12 | Quadratic Reciprocity and Primality Test. | 23/04/18 | Fan |
| 23/04/19 | 13 | Quadratic Congruences and Cryptography. | 23/04/25 | Yunpeng |
| 23/04/26 | 14 | Review exercises | not graded | |
| 23/05/01 | Mock Exam | not graded |
Written assignments will be due in the night between Tuesday and Wednesday, more precisely on Wednesday early morning at 5:00am. Submission is online, via Courseworks, at the Gradescope page.
We will accept late homework, but we deduct 10% of the points for every day of lateness.
There will be two midterms, the first on Wednesday February 15th, the second on Wednesday March 29th, both during the usual class time.
Projected schedule for the final exam: Wednesday May 10th, 9am– Noon, in Room 312 Mathematics. The date will be confirmed by the University.
You must plan to take the midterm and final exams at the scheduled time, so please make your plans accordingly. Besides students with disabilities having prior arrangements with DS or CARDS, the only exceptions will be for those with an incapacitating illness, a serious family emergency, or situations of comparable gravity. In this case you will need to ask your advising dean to send me a note to confirm your situation of need. If your motivation seems reasonable, I will use the grade of your final exam as grade for your midterm. For the final exam, we will organize a make-up exam. Incompletes can be granted only by your advising dean and only in the circumstances mentioned above.
Anyone guilty of academic dishonesty, such as cheating on an exam or helping someone else to cheat, will fail the course and faces further academic discipline.
Homework 10%, midterms 25% each, final 40%.