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
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
Begin II.2: The Legendre symbol, quadratic residues, quadratic reciprocity.
2006.11.22: End I.3. Discuss RSA again. Fast
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).