Hellman, Martin E.; Reyneri, Justin M. Fast computation of discrete logarithms in \(\mathrm{GF}(q)\). (English) Zbl 0514.94013 Advances in cryptology, Crypto 1982, Proc. Workshop Santa Barbara/Calif. 1982, 3-13 (1983). Summary: The Merkle-Adleman algorithm computes discrete logarithms in \(\mathrm{GF}(q)\), the finite field with \(q\) elements, in subexponential time, when \(q\) is a prime number \(p\). This paper shows that similar asymptotic behavior can be obtained for the logarithm problem when \(q = p^m\), in the case that \(m\) grows with \(p\) fixed. A method of partial precomputation, applicable to either problem, is also presented. The precomputation is particularly useful when many logarithms need to be computed for fixed values of \(p\) and \(m\). For the entire collection see [Zbl 0511.00040]. Page: −5 −4 −3 −2 −1 ±0 +1 +2 +3 +4 +5 Show Scanned Page Cited in 3 Documents MSC: 94A60 Cryptography 11T71 Algebraic coding theory; cryptography (number-theoretic aspects) 11Y16 Number-theoretic algorithms; complexity Keywords:finite field; subexponential time; partial precomputation; cryptography PDF BibTeX XML Full Text: DOI