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.

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.


Ben Lynn blynn@cs.stanford.edu 💡