A subexponential-time algorithm for computing discrete logarithms overGF(p^2)
- 1 July 1985
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 31 (4), 473-481
- https://doi.org/10.1109/tit.1985.1057075
Abstract
An algorithm for computing discrete logarithms over GF(p^{2}), wherepis a prime, in subexponential time is described. The algorithm is similar to the Merkle-Adleman algorithm for computing logarithms over GF(p), but it uses quadratic fields as the appropriate algebraic structure. It also makes use of the idea of a virtual spanning set due to Hellman and Reyneri for computing discrete logarithms over GF(p^{m}), formgrowing andpfixed.Keywords
This publication has 9 references indexed in Scilit:
- Discrete logarithms in finite fields and their cryptographic significancePublished by Springer Science and Business Media LLC ,2000
- Fast evaluation of logarithms in fields of characteristic twoIEEE Transactions on Information Theory, 1984
- Computing Logarithms in Finite Fields of Characteristic TwoSIAM Journal on Algebraic Discrete Methods, 1984
- Asymptotically fast factorization of integersMathematics of Computation, 1981
- A subexponential algorithm for the discrete logarithm problem with applications to cryptographyPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1979
- New directions in cryptographyIEEE Transactions on Information Theory, 1976
- On factorisation, with a suggested new approachMathematics of Computation, 1975
- Topics in Multiplicative Number TheoryLecture Notes in Mathematics, 1971
- The Least Quadratic Non ResidueAnnals of Mathematics, 1952