Number Theory
I’m taking a loose informal approach, since that was how I learned. Once you have a good feel for this topic, it is easy to add rigour.
More formal approaches can be found all over the net, e.g: Victor Shoup, A Computational Introduction to Number Theory and Algebra.
One reader of these notes recommends I.N. Herstein, 'Abstract Algebra' for further reading.
I built a PDF version of these notes.
Overview
I have tried to order my pages so that the parts most relevant to cryptography are presented first.
- Modular Arithmetic
-
We begin by defining how to perform basic arithmetic modulo \(n\), where \(n\) is a positive integer. Addition, subtraction, and multiplication follow naturally from their integer counterparts, but we have complications with division.
- Euclid’s Algorithm
-
We will need this algorithm to fix our problems with division. It was originally designed to find the greatest common divisor of two numbers.
- Division
-
Once armed with Euclid’s algorithm, we can easily compute divisions modulo \(n\).
- The Chinese Remainder Theorem
-
We find we only need to study \(\mathbb{Z}_{p^k}\) where \(p\) is a prime, because once we have a result about the prime powers, we can use the Chinese Remainder Theorem to generalize for all \(n\).
- Units
-
While studying division, we encounter the problem of inversion. Units are numbers with inverses.
- Exponentiation
-
The behaviour of units when they are exponentiated is difficult to study. Modern cryptography exploits this.
- Order of a Unit
-
If we start with a unit and keep multiplying it by itself, we wind up with 1 eventually. The order of a unit is the number of steps this takes.
- The Miller-Rabin Test
-
We discuss a fast way of telling if a given number is prime that works with high probability.
- Generators
-
Sometimes powering up a unit will generate all the other units.
- Cyclic Groups
-
We focus only on multiplication and see if we can still say anything interesting.
- Quadratic Residues
-
Elements of \(\mathbb{Z}_n\) that are perfect squares are called quadratic residues.
Bonus Material
The other topics are less relevant to cryptography, but nonetheless interesting.