Introduction to cryptography.

Book: N. Koblitz: A Course in Number Theory and Cryptography.
Graduate Texts in Mathematics 114, 2nd ed., 1994, Springer-Verlag 1994
ISBN: 0-387-94293-9

Lectures: Wednesdays 10-12 in Aud. 7, Fridays 13-15 in Aud. 10. Course language English.
Period: Block 1: 30. August - 5. November.
First lecture on Wednesday, September 1, last lecture on Friday, November 5.

Planned content of the course: Public Key cryptography, complexity of arithmetic operations, primality testing, factorization of integers, discrete logarithms.


2004.11.05:  We finished the discussion of the AKS primality test.

2004.11.03:  Let's look at the Agrawal-Kayal-Saxena deterministic, polynomial-time primality test. I will discuss both the (almost) original form of the theorem (but with a modification due to Bernstein) as well as the more streamlined after an improvement by H. Lenstra. I will use a preprint by Bernstein: as well as the preprint by Agrawal-Kayal-Saxena:

In the first lecture I will discuss Theorem 2.1 as in the preprint by Bernstein.

You can look at the following expository article for some background info: F. Bornemann: `PRIMES is in P: a breakthrough for "everyman"', Notices Amer. Math. Soc. 50 (2003), 545--552.
The article is freely available online:


2004.10.29:  The Pohlig-Hellman method for computing discrete logarithms.
I will discuss the original paper by Pohlig and Hellman: `An improved algorithm for computing logarithms over $GF(p)$ and its cryptographic significance', IEEE Trans. Inform. Theory 24 (1978), 106--110. Photocopies of the paper will be handed out.

2004.10.27:  IV.3: Discrete logarithms and index calculus. Seminar by Jes Kamstrup Hansen.


2004.10.23:  We finished the discussion of Dixon's factoring algorithm using the notes psi.pdf

2004.10.20:  We continue the discussion of Dixon's factoring algorithm using my notes:  psi.pdf
Today we discussed complexity and finished sections 4.1.1, 4.1.2, and the beginning of 4.2 until and including Prop. 5.


2004.10.13 + 2004.10.15:  Autumn vacation.


2004.10.08:  Begin V.3: Fermat factorization. After the first section about Fermat factorization I will discuss the 'factor base algorithm' (Dixon's algorithm) in greater detail than in the book, - especially in connection with the complexity estimates. I will use these notes that you can download and print out:  psi.pdf
Today we discussed Dixon's algorithm: Section 4.1 until and including section 4.1.1 of the notes. I then started the discussion of the psi-function and we got to the beginning of page 2 of the notes.

2004.10.06:  Exercise 21 of section II.2. The notion of a probabilistic algorithm.  Square roots modulo p.


2004.10.01:  Discussion of the Miller-Rabin primality test continued. A little about the generalized Riemann hypothesis.

2004.09.29:  V.1: Primality testing, continued. Seminar by Ahmet Tas.
Further discussion of the Miller-Rabin primality test.


2004.09.24:  Begin V.1: Primality testing. Seminar by Kasper Maes.
V.1: Primality testing, continued. Seminar by Ahmet Tas.

2004.09.22:  II.2: The Legendre symbol, quadratic residues. Quadratic reciprocity without proofs. The Jacobi symbol and the computation of it.


2004.09.17:  II.2: Survey of finite fields. Seminar by Jakob Neesgård.

2004.09.15:  End I.3. Discuss RSA again.


2004.09.10:  I.2, I.3: Euclidean algorithm and modular arithmetic.

2004.09.08:  I.1: The notion of complexity. Complexity of the basic arithmetic operations: Addition, subtraction, multiplication, division with remainder, square roots. Big O and little o notation, the notions of polynomial, exponential, and subexponential complexity.


2004.09.03:  Cancelled.

2004.09.01:  I think it is a little strange to start the course without discussing first the very basic principles of (Public Key) cryptography. Accordingly, I will not start with chapter 1, but instead with the qualitative discussions of crypto systems in chapters 3 and 4. Then we begin discussing complexity as in chapter 1. After chapter 1 we return to discuss RSA again.
The qualitative material of chapters 3,4 that I'm referring to is this: pp. 54-66, pp. 83-91, p. 93, pp. 97-99, p. 100-101 (ElGamal).