Number Theory and Cryptography
Welcome to the Number Theory and Cryptography course page. Here you will find all relevant information regarding the course outline, lecture schedules, homework assignments, and additional resources.
Who, When and Where?
Instructor: Chao Qin
Teaching Assistants: Wenhao Tong and Yingshu Wang
Lecture Times: Tuesdays from 9:55 AM to 12:20 PM and Thursdays from 1:30 PM to 3:05 PM
Location: Building 11, Room 112
Course Overview and Contents
Number Theory and Cryptography combine abstract mathematical theories with practical applications in security. This course covers foundational and advanced topics such as prime numbers, factorization, modular arithmetic, and cryptographic protocols. We will also delve into elliptic curves and their applications in cryptography, alongside exploring various cryptographic systems including public-key cryptosystems and the RSA algorithm. Optional homework and computational exercises using Sagemath will provide practical insights into theoretical concepts.
Structure of the Classes
Lectures will be held twice a week on Tuesdays from 9:55 AM to 12:20 PM and Thursdays from 1:30 PM to 3:05 PM in Building 11, Room 112. Each class will include a lecture segment and an interactive exercise session to deepen understanding and facilitate active engagement with the material.
Lecture Schedule and Notes
- Lecture 1: May 7, Course info and Prime Numbers - Slides | Notes
- Lecture 2: May 9, Congruences Modulo $n$ - Slides | Notes
- Lecture 3: May 14, Chinese Remainder Theorem, Computing Inverse, Primality Test- Slides | Notes
- Lecture 4: May 16, Structure of $\mathbb{Z}/p\mathbb{Z}$ - Slides | Notes
- Lecture 5: May 21, Public-key Cryptography - Slides | Notes
- Lecture 6: May 23, RSA Cryptosystem - Slides | Notes
- Lecture 7: May 28, Quadratic Reciprocity - Slides | Notes
- Lecture 8: May 30, Finding Square Roots, In-calss Midterm - Slides | Notes
- Lecture 9: June 4, Continued Fractions - Slides | Notes
- Lecture 10: June 6, Sum of Two Squares, Sum of Four Squares - Slides | Notes
- Lecture 11: June 11, Introduction to Elliptic Curves- Slides | Notes
- Lecture 12: June 13, Elliptic Curves in Cryptography - Slides | Notes
- Lecture 13: June 18, Student Presentations on Selected Topics - Slides | Notes
- Lecture 14: June 20, Final Review and Exam Preparation - Slides | Notes
Homework Assignments
- Homework 1: Problems on Divisibility and Primes - Due Date: May 20
- Homework 2: Modular Arithmetic Exercises - Due Date: May 27
- Homework 3: Implementing RSA Algorithm - Due Date: June 3
- Homework 4: Quadratic Reciprocity questions - Due Date: June 10
- Homework 5: Continued Fractions - Due Date: June 17
- Homework 6: Elliptic Curve Cryptography Problems - Due Date: June 24
Midterm Test
In-class Midterm Test on May 30th during the regular lecture time.
References
- Stein, W. (2009). Elementary number theory: Primes, congruences, and secrets. Springer. Find this book online
- Stallings, W. (2017). Cryptography and network security: Principles and practice (7th ed.). Pearson. Find this book online
- Hoffstein, J., Pipher, J., & Silverman, J. H. (2008). An introduction to mathematical cryptography. Springer. Find this book online