Discrete logarithms in \(\mathrm{GF}(p)\) (Q1094455): Difference between revisions

Authors' introduction: ``The authors examine the problem of finding logarithms in a field \(\mathrm{GF}(p)\), where \(p\) is a prime; that is, given integers \(a\), \(b\) and a prime \(p\), producing an integer \(x\) such that \(a^x\equiv b \bmod p\), if such an \(x\) exists. Let \(L\) denote any quantity that satisfies \[ L=\exp ((1+o(1) \sqrt{\log p \log \log p}), \] where \(\log x\) is the natural logarithm of \(x\), and let \(L[c]=L^c\). The fastest previously published algorithms and their adaptations can be shown heuristically to have running times of about \(L[c]\) for some constants \(c>1\), with \(c\) typically around \(3/2\) or \(2\). In this paper the authors present several algorithms whose heuristic running time is \(L[1]\) for the initial precomputation phase that is required for each prime \(p\). (After that phase is completed, individual logarithms in \(\mathrm{GF}(p)\) can be computed much faster: heuristically \(L[1/2]\) for several of the algorithms.) This is the same estimate as holds for the fastest known algorithms for factoring integers of size about \(p\). It is quite different from the situation of fields \(\mathrm{GF}(2^n)\) (or more generally, fields of \(\mathrm{GF}(q^n)\) where \(q\) is held fixed and \(n\to \infty)\) where the first author has shown that discrete logarithms can be computed in time \[ \exp (c\, n^{1/3} (\log n)^{2/3} \] for some \(c>0\) depending on \(q\).'' For the time being with this paper the exciting development about the ``discrete logarithm chase'' seems to have reached certain rest: As these results are of immediate importance for research in the security analysis of cryptographic systems, it should be noted that in spite of the outstanding results presented discrete log-based cryptosystems are not broken, as serious secure concepts will be based on fields of large enough size.