> b) An exposition of the Lenstra or Morain improvements

I don't think that François Morain improved the algorithm. His paper just

indicates the proof of AKS theorem, the results of his implementation

and a comparison of performance with ECPP.

Bernstein explains Lenstra's improvement in his paper.

The conditions

n^(r-1)/q (mod r) != {0, 1}

and (q+s-1, s) >= n^{2 sqrt(r)}

can be replaced by

n is a primitive root modulo r

and (phi(r)+s-1, s) >= n^sqrt(r)

then we can use smaller values for r and s and it speeds up the algorithm.

Yves