A rigorous proof of the Waterloo algorithm for the discrete logarithm problem
type: Item
instance of: scholarly article
title: A rigorous proof of the Waterloo algorithm for the discrete logarithm problem
zbMATH Open document ID: 1006.11072
DOI: 10.1023/A:1016521712726
author: Michael Drmota
author: Daniel Panario
published in: Designs, Codes and Cryptography
publication date: 2002-08-21T00:00:00Z
review text: 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)].
reviewed by: Tanja Lange
Mathematics Subject Classification ID: 11T71
Mathematics Subject Classification ID: 11Y16
Mathematics Subject Classification ID: 68P25
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 1785711
zbMATH Keywords: discrete logarithm problem
zbMATH Keywords: finite fields
zbMATH Keywords: smooth polynomials
zbMATH Keywords: generating functions
MaRDI profile type: Publication
full work available at URL: a:1016521712726
OpenAlex ID: W1596459745
Recommended article: A deterministic algorithm for the discrete logarithm problem in a semigroup
Recommended article: Public Key Cryptography - PKC 2006
Recommended article: ON GENERIC COMPLEXITY OF THE DISCRETE LOGARITHM PROBLEM
Recommended article: A variant of the Galbraith-Ruprai algorithm for discrete logarithms with improved complexity
Recommended article: A simplified approach to rigorous degree 2 elimination in discrete logarithm algorithms
Recommended article: Q3792628
Recommended article: Complexity of a determinate algorithm for the discrete logarithm
Recommended article: Q5750402
Recommended article: A Subexponential Algorithm for Discrete Logarithms Over all Finite Fields
Recommended article: Q4341740
description: scientific article; zbMATH DE number 1785711