Number theory

Note created for an introductory course on cryptography in the fall term of 2010. The note just covers the very basics needed.

To view or download

Best for on-screen viewing: A5 size (PDF).

Best for printing: A4 size (PDF).
(If you need to print on US letter paper, be sure to ask your printer driver to reduce the size to fit the paper.)

Version history

• The current version is dated 2011-10-04. Lemma 12 now has a much more direct proof. (What was I thinking?)
• In the version dated 2011-09-08, there are some minor cosmetic changes, plus I ensure that the message in the ElGamal scheme is not zero. I also point out the security equivalence between ElGamal and Diffie–Hellman.
• In the version dated 2010-11-02, the section on Pedersen commitment has been expanded to include the discrete log hash, which is based on the same mathematics. Also, a new section on coin tossing has been added at the end.
• The version dated 2010-10-15 had new sections on quadratic residues, factoring, the discrete logarithm problem, and the Pedersen commitment scheme.
• In the version dated 2010-09-24 I have corrected the definition of Carmichael numbers, and added some material on finding safe primes and generators.
• The version dated 2010-09-21 has a new section on primality testing, and some minor misprints have been fixed. If you don't care about the misprints, just printing out the last two pages of the A4 version or the last three pages of the A5 version will give you the new material.
• The version dated 2010-09-07 is almost doubled in size since the first version. There are new sections on modular exponentiation, with applications to Diffie–Hellman key exchange and the ElGamal cryptosystem, and on the Chinese remainder theorem, Fermat's little theorem, the Euler φ function, and the RSA cryptosystem.
• The first version is dated 2010-09-03. The note was not finished. More material will be added.