**Weekly
updates:**

**2007.01.24:** We finish the discussion of the
Agrawal-Kayal-Saxena primality test.

**2007.01.22:** The Agrawal-Kayal-Saxena primality test,
continued.

**2007.01.17:** We finish the discussion of the
Pohlig-Hellman algorithm for computing discrete logs.

After that we start discussing the Agrawal-Kayal-Saxena primality test.

**2007.01.15:** We start discussing the so-called Pohlig-Hellman
algorithm for computing discrete logs. We use their original article:

S. C. Pohlig, M. E. 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 article will be handed out at the lecture.

**2007.01.10:** We finished discussing the complexity
of Dixon's factoring algorithm. This is the rest of section 4.2 of the notes.

We started the discussion of the discrete logarithm problem in finite fields.

Today we first looked at the attack via the so-called 'index calculus'. This is described in section IV.3 of the book, pp. 103--106. I described it in slightly more general terms and mentioned the best known results on the index calculus method for the discrete logaritm problem in finite fields.

**2007.01.08: **We begin discussing the complexity of
Dixon's factoring algorithm. We finished proving proposition 5 of the notes.

**2007.01.03:** We proved some theorems that will be used
as tools in the complexity analysis of of Dixon's factoring algorithm:
Elementary lower bound for the psi-function, Wallis' product, and Stirling's
formula.

**2006.12.18:** 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. We will use my notes on the
psi-function as the basis of this discussion.

Today we discussed Fermat
factorization, the structure of Dixon's algorithm, introduced the psi-function,
and mentioned some of the theorems concerning it, including the elementary lower
bound that we will prove next time.

**2006.12.13:** We prove Prop. V.1.7 and make further
remarks about the Miller-Rabin primality test and the generalized Riemann
hypothesis.

**2006.12.11:** V.1, primality testing, continued: Strong
pseudoprimes, the Miller-Rabin primality test. We finished the proof that strong
pseudoprimes are Euler pseudoprimes, and we also proved 2 lemmas in preparation
for the proof of Prop. V.1.7.

**2006.12.06:** V.1, primality testing: Carmichael numbers,
pseudoprimes, Euler pseudoprimes, the Solovay-Strassen primality test. Exercise
21 to II.2, p. 52 in the book.

**2006.12.04:** End II.2: Proof of reciprocity for the Jacobi
symbol. Computing square roots modulo p; the notion of a probabilistic
algorithm.

Begin V.1: Primality testing.

**2006.11.29:** II.2 continued: Proof of quadratic reciprocity.
The Jacobi symbol and the computation of it.

**2006.11.27:** II. 1: Survey of finite fields
continued.

Begin II.2: The Legendre symbol, quadratic residues, quadratic
reciprocity.

**2006.11.22:** End I.3. Discuss RSA again. Fast
exponentiation.

Begin II.1: Survey of finite fields.

**2006.11.20:** I.2, I.3: Euclidean algorithm and modular
arithmetic.

**2006.11.15:** 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.

**2006.11.13:** We will start with the qualitative discussions
of crypto systems in chapters 3 and 4; this is pp. 54-66, pp. 83-91, p. 93, pp.
97-99, p. 100-101 (ElGamal).