Number Theory

I developed an upper-level number theory course for Bard College which I taught in the spring of 2016. This page contains information about this course.

Summary

The course was designed for a mix of students interested in pure and applied mathematics, and covered both theoretical topics (such as the classification of finite fields and the proof of quadratic reciprocity using Gauss sums) and applied topics (such as primality tests, the RSA cryptosystem, and Diffie–Hellman key exchange). Most of the students were sophomore, junior, or senior mathematics majors and had some programming experience.

The textbook for the course was An Introduction to Number Theory with Cryptography by Kraft and Washington.

Homework Assignments

Here are the weekly homework assignments for the course, which were worth 50% of the course grade. These assignments are a mixture of problem-solving, formal proofs, and computer analysis in SageMath or Mathematica. Students were encouraged to work together on the homework but were required to write up their own solutions individually in LaTeX.

• Homework 1 (Recursive Sequences, Primes that are 3 Modulo 4)
• Homework 2 (Greatest Common Divisors, Sieve of Eratosthenes, Euclidean Algorithm)
• Homework 3 (Extended Euclidean Algorithm, Linear Diophantine Equations)
• Homework 4 (Rational and Irrational Numbers, Factorial Digits)
• Homework 5 (Repeated Squares, Multiplicative Inverses, Euler's Theorem)
• Homework 6 (Chinese Remainder Theorem, Euler's Totient Function)
• Homework 7 (The RSA Cryptosystem)
• Homework 8 (Cyclotomic Polynomials, Orders of Elements in Finite Fields)
• Homework 9 (Fermat Primality Test, Primitive Elements, Diffie–Hellman Key Exchange)
• Homework 10 (Discrete Logarithms, Quadratic Reciprocity,
• Homework 11 (Polynomials Over Fields, Lucas-Lehmer primality test)
• Homework 12 (Finite Fields, Primes that are 1 Modulo 4)

Takehome Exams

There were two takehome exams for the course, both of which were worth 20% of the grade.

• Takehome Midterm
• Takehome Final

Notes

Though the course used a textbook, I supplemented this with notes on some more advanced theoretical material:

• Notes: Fields and Cyclotomic Polynomials
• Notes: Gauss Sums
• Notes: Number Theory for Polynomials
• Notes: Finite Fields
• Notes: Minimal Polynomials
• Notes: Classification of Finite Fields

Syllabus

Here was the syllabus for the course.

Textbook Information

The textbook is An Introduction to Number Theory with Cryptography by Kraft and Washington. You will need a copy of the textbook for reading and homework problems, though you do not need to bring it to class. An electronic version of the book an be rented for $35 from Amazon.com, or you can buy an electronic or paper version for $88.

You may also find the free online textbook Elementary Number Theory: Primes, Congruences, and Secrets by Stein helpful, especially if you're planning to to use SageMath for computer programming.

Course Description

This is a proofs-based introduction to number theory and cryptology. Topics will be a mix of theoretical, computational, and applied number theory, and we will make significant use of computers to explore and test conjectures and implement number-theoretic and cryptological algorithms. Possible topics include the fundamental theorem of arithmetic, congruences, public-key cryptosystems, quadratic reciprocity, factorization algorithms, Diophantine equations, continued fractions, and an introduction to elliptic curves.

Prerequisites

The main prerequisite is Math 261 (Proofs & Fundamentals) or the equivalent. The course will also assume some familiarity with computer programming, such as that obtained from CMSC 143 (Object-Oriented Programming) or MATH 323 (Dynamical Systems). Some experience with abstract algebra (such as MATH 332) may be helpful, but is not necessary.

Homework, Exams, and Grading

Homework

Homework assignments will be a mixture of formal proofs, problem-solving, and computer analysis. You are encouraged to work together on the homework, but you should write up your own solutions individually, and you must acknowledge any collaborators.

All proofs must be written in LaTeX and submitted to me by e-mail. Computer programs may be written in the language of your choice (e.g. SageMath or Mathematica) and their source code submitted via e-mail.

Final Project

There will be a final project, on a topic of your choice. I am happy to allow group projects, though each member of a group must contribute as much effort as a student working individually. A typical project for a pair of students consists of a 10–15 minute class presentation as well as perhaps a computer program or a few pages of written proofs. More details on the final project will be given as we approach the end of the semester.

Exams and Grading

The grade will be based on the weekly homework, the takehome midterm exam, the takehome final exam, and the final project:

Project Information

Part of the requirements for this class include a final project. Here is some basic information about the project:

• • Though individual projects are allowed, I would prefer for you to work together in groups of two or three.
• • The project must involve a short in-class computer presentation, of the following length:
  • • Individual Project: 4–5 minute presentation
  • • Two-Person Project: 8–10 minute presentation
  • • Three-Person Project: 12–15 minute presentation
• • All projects must include a short paper, and may also involve a Mathematica or SageMath notebook. For a purely theoretic project, the paper should be about 4-5 pages per person, and must include at least one proof. Alternatively, you may include a significant Mathematica or SageMath notebook as part of your project, in which case your paper can be shorter (2-3 pages per person) and need not contain any proofs.

Project Topics

Good topics include any aspect of number theory or crypotgraphy that we have not covered in class. Some possibilities include:

• • A discussion or exploration of an open problem in number theory, such as the abc conjecture, the Collatz conjecture, the Goldbach conjectures, Legendre's conjecture, the Catalan's conjecture, the Erdős–Straus conjecture, the congruent number problem, or the existence of a perfect cuboid.
• • A discussion and implementation of an important algorithm or cryptosystem that we did not get a chance to cover, such as pseudorandom number generators such as linear feedback shift registers or the Mersenne twister, the Advanced Encryption Standard (AES) (which is based on the Rijndael S-box), checksums and the Luhn algorithm, error-correcting codes such as the BHC code, fast multiplication algorithms such as the Karatsuba algorithm, the sieve of Atkin for listing prime numbers, Pollard's rho algorithm for integer factorization, the Miller-Rabin primality test, elliptic curve cryptography, quantum computing and Shor's algorithm.
• • A discussion of some theoretical topic that we did not get the chance to cover, including continued fractions, p-adic numbers, elliptic curves, primes in arithmetic progression (including Dirichlet's theorem and the Green-Tao theorem), Egyptian fractions, Chebyshev's bias, Bertrand's postulate, the Ulam spiral, Mill's constant and other formulas for primes, families of numbers such as amicable numbers, abundant numbers, weird numbers, deficient numbers, and superperfect numbers, and so forth.
• • A discussion and/or implementation of anything related to public key infrastructure or the real-world depolyment of cryptographic protocols. Depending on the topic, this may or may not involve writing computer code. Possible topics include Pretty Good Privacy and the OpenPGP standard, certificate authorities and public-key certificates (including possibly the X.509 standard, or a discussion of webs of trust), crypotcurrencies such as bitcoin and the associated cryptographic hash functions, electronic voting and E2E systems, message authentication codes (such as CMAC), and security of the Domain Name System (including the DNSSEC protocol).