Number Theory & Cryp

Course

Number Theory and Cryptography - Math UN3020.
Spring 2022.
Columbia University.

Lectures

Classroom: Room 312 Mathematics.
During the first two weeks of classes, the lectures will be online via Zoom. The Zoom link for the online lectures will be shared on Courseworks.
Mo, We 10:10am-11:25am.

Instructor

Name: Daniele Alessandrini.
Contact: daniele.alessandrini@gmail.com.
Office: 624 Mathematics.

Office hours: Tentative schedule: Mo 11:30am-12:30pm, We 9am-10am. The office hours will be in Room 622 Mathematics.

Help Room

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.

TAs

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.

Name	Help Room Schedule
Jingbo Wan	Thu 9am-12pm
Haodong Yao	Mon 5-8pm
Lori Leu	Wed 2-4pm
Ahmed Medhat Shaaban	Mon 4-6pm

Syllabus

The Syllabus for this course.

Required text

There is no required text. We will mainly follow the notes by Gordan Savin: Numbers, Groups and Cryptography. They are available online.

Course Outline

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.

Lectures

Date	No	Topic	Textbook Reference
22/01/19	01	Introduction. Numbers, operations, groups and rings.	Section 2.1, 3.1.
22/01/24	02	Rings and Fields	Section 3.1.
22/01/26	03	Mathematical Induction. Divisibility.	n/a
22/01/31	04	Euclidean algorithm.	Sec. 1.1.
22/02/02	05	Bézout's Identity, Euclid's Lemma, Diophantine Equations.	Sec. 1.2.
22/02/07	06	Prime numbers.	Sec. 1.3.
22/02/09	07	Prime factorization. Totient Function. Congruences.	Section 1.3, 2.2.
22/02/14	08	Infinitude of primes. Modular arithmetic.	Section 4.1, 2.3.
22/02/16	09	Zero-divisors and invertibility modulo n. Some cryptography.	Section 2.3.
22/02/21	10	Some cryptography. Linear Congruences.	Section 2.5.
22/02/23	11	Chinese Remainder Theorem. Secret Sharing.	Section 2.5.
22/02/28	12	Secret Sharing. Totient Function. Order of an element.	Section 2.4, 2.5.
22/03/02	13	Lagrange's Theorem. Euler's Theorem. Public Key Cryptography.	Section 2.4.
22/03/07	14	RSA algorithm.	Section 10.2.
22/03/09		Midterm.
22/03/14		Spring Break.
22/03/16		Spring Break.
22/03/21	15	RSA example. Polynomials.	Section 10.2.
22/03/23	16	Polynomial division. Roots.
22/03/28	17	Property of the totient funcition, Roots of unity.	Section 5.2, 5.3.
22/03/30	18	Roots of unity, Discrete logarithm.	Section 5.3, 5.4.
22/04/04	19	Diffie Hellmann and ElGamal algorithms.	Section 10.1, 10.3.
22/04/06	20	Quadratic Residues. Legendre Symbols.	Section 6.1
22/04/11	21	Quadratic Reciprocity.	Section 6.3, 6.4.
22/04/13	22	Quadratic Residues modulo n. Jacobi Symbols. Goldwasser-Micali Cryptosystem.	n/a
22/04/18	23	Example of Goldwasser-Micali. Miller-Rabin Primality Test.	Section 11.1.
22/04/20	24	Miller-Rabin Primality Test and Quadratic Sieve.	Section 11.1, 11.4.
22/04/25	25	Quadratic Sieve and Shor's algorithm.	Section 11.4.
22/04/27	26	Shor's algorithm and random number generators.
22/05/02	27	Review Lecture

One year of Calculus; you will also need some familiarity with proofs or a willingness to learn.

Homework sheets

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
22/01/26	01	Numbers	21/02/01	Haodong
22/02/02	02	Divisors	22/02/08	Lori
22/02/09	03	Primes	22/02/15	Jingbo
22/02/16	04	Modular Arithmetic	22/02/22	Ahmed
22/02/23	05	Linear Congruences	22/03/01	Lori
22/03/02	06	Lagrange's Theorem	22/03/08	Ahmed
22/03/09	07	Binomial Congruences	22/03/22	Lori
22/03/23	08	Polynomial division	22/03/29	Haodong
22/03/30	09	Roots of unity	22/04/05	Jingbo
22/04/06	10	Quadratic Residues	22/04/12	Haodong
22/04/13	11	Quadratic Reciprocity	22/04/19	Jingbo
22/04/20	12	Primality test and Factorization	22/04/26	Ahmed
22/04/27	13	Factorization and review	not graded
22/05/07		Mock Exam	not graded

Submission

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.

Late hand in

We will accept late homework, but we deduct 10% of the points for every day of lateness.

Midterm exam

There will be one midterm exam on Wednesday March 9th during the usual class time.

Final exam

The final exam will be on Wednesday May 11th, 9am– Noon, in Room 312 Mathematics.

Exam dates

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.

Academic dishonesty

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.

Grading

Homework 15%, midterms 35%, final 50%.