A rigorous proof of the Waterloo algorithm for the discrete logarithm problem (Q1611366)

The index calculus attack is a sub-exponential algorithm to compute discrete logarithms in finite fields. For fields of small characteristic, especially \(\mathbb{F}_{2^n}\), \textit{D. Coppersmith}'s variant [IEEE Trans. Inf. Theory 30, 587-594 (1984; Zbl 0554.12013)] is (heuristically) most efficient. A further algorithm specially designed for this case is the Waterloo algorithm [Advances in cryptology, Proc. Workshop, Santa Barbara/Calif. 1984, Lect. Notes Comput. Sci. 196, 73-82 (1985; Zbl 0574.94012)] by \textit{I. F. Blake, R. C. Mullin}, and \textit{S. A. Vanstone}. The present article manages to give proofs for the heuristic arguments used to estimate the running time. The main step is to compute the probability that two polynomials of degree at most \(n/2\) factor into irreducible polynomials of degree at most \(m\), where \(m\) is a parameter of the algorithm. To reach this aim the authors estimate the number of \(m\)-smooth polynomials of bounded degree and coprime pairs of such polynomials. The main tool used to derive these results are generating functions for polynomials and the saddle point method as in \textit{A. L. Odlyzko} [Advances in cryptology, Proc. EUROCRYPT 84, Workshop Paris 1984, Lect. Notes Comput. Sci. 209, 224-314 (1985; Zbl 0594.94016)].