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

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