Algorithmic Number Theory
Math 781 - Spring 2024
Announcements
This page contains some information that can be helpful before you register for the course. After the registration, we will be using odtuclass. You should follow odtuclass and check your emails regularly for important announcements during the semester.
Course Objectives
The algorithmic number theory connects the classical number theory topics and the theory of computational complexity. In this course, we will study algorithms for finding integer solutions to certain equations, polynomial factorization, primality testing, and integer factorization. We will also study how the objects in question can be efficiently implemented on a computer. The algorithmic number theory problems are important for their mathematical interest and application to secure information exchange, such as RSA and elliptic curve cryptography.
Lectures and Office Hours
The first meeting is on Wednesday, February 14 at 14:00 in M215. The lecture hours will be decided during this meeting.
Homeworks, Exams and Grading
Homeworks will be assigned on a regular basis and there will be 3-5 homework sets by the end of the semester. There will be one midterm and a final. The time and the method of each exam will be announced later.
Midterm, 30 points - around the 8th week.
Final, 30 points - during the final exam period.
Homework, 40 points.
Homework Policy: You should write your solutions on your own. You are allowed to consult other people's solutions for homework problems, but you must express everything in your own words. If you copy a solution, which is referred to as cheating, you will probably gain nothing and may encounter penalties.
Textbooks and Tentative Course Outline
Cohen, H., A Course In Computational Algebraic Number Theory.
Bach E. and Shallit J., Algorithmic Number Theory.
Find a tentative outline below for the whole semester. For each week, we will attempt to cover the indicated pages of Cohen's textbook.
Week 1: February 19 - February 23, Pages 1-7.
Introduction. Basic programming commands. Big-O notation.
Pari/GP tutorial.
Week 2: February 26 - March 1, Pages 8-18.
The powering algorithms. The Euclidean algorithm for integers.
Week 3: March 4 - March 8, Pages 19-30.
The Chinese remainder theorem. Computations modulo n. Legendre-Jacobi-Kronecker symbol.
Week 4: March 11 - March 15, Pages 31-45.
Computing square roots modulo p. Power detection.
Week 5: March 18 - March 22, Pages 46-65.
A survey of algorithms for linear algebra.
Week 6: March 25 - March 29, Pages 109-117.
Basic algorithms on polynomials. The Euclidean algorithm for polynomials.
Week 7: April 1 - April 5, Pages 124-132.
Factorization of polynomials over finite fields.
Holiday Break?
Week 8: April 15 - April 19, Pages 133-141.
Factorization of polynomials over rational numbers.
Week 9: April 22 - April 26, Pages 153-167.
Algebraic numbers, trace, norm, discriminants, and integral bases.
Week 10: April 29 - May 3, Pages 223-251.
Imaginary quadratic fields.
Week 11: May 6 - May 10, Pages 262-278.
Real quadratic fields.
Week 12: May 13 - May 17, Pages 419-444.
Historical examples of factoring and primality testing.
Week 13: May 20 - May 24, Pages 445-476.
Modern primality tests.
Week 14: May 27 - May 31, Pages 477-504.
Modern factoring methods.
PARI / GP
The software PARI / GP is very simple to learn and
extremely strong to do computations with.