zbMATH — the first resource for mathematics

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].

94A60 Cryptography
11T71 Algebraic coding theory; cryptography (number-theoretic aspects)
11Y16 Number-theoretic algorithms; complexity
Full Text: DOI