Abstract
Recently, Shirokauer’s algorithm to solve the discrete logarithm problem modulo a prime p has been modified by Matyukhin, yielding an algorithm with running time \(L_{p}[\frac{1}{3},1.09018...]\), which is, at the present time, the best known estimate of the complexity of finding discrete logarithms over prime finite fields and which coincides with the best known theoretical running time for factoring integers, obtained by Coppersmith. In this paper, another algorithm to solve the discrete logarithm problem in \(\mathbb{F}^{*}_{p}\) for p prime is presented. The global running time is again \(L_{p}[\frac{1}{3},1.09018...]\), but in contrast with Matyukhins method, this algorithm enables us to calculate individual logarithms in a separate stage in time \(L_{p}[\frac{1}{3},3^{1/3}]\), once a \(L_{p}[\frac{1}{3},1.09018...]\) time costing pre-computation stage has been executed. We describe the algorithm as derived from [6] and estimate its running time to be \(L_{p}[\frac{1}{3},(\frac{64}{9})^{1/3}]\), after which individual logarithms can be calculated in time \(L_{p}[\frac{1}{3},3^{1/3}]\).
Chapter PDF
Similar content being viewed by others
References
Canfield, E., Erdös, P., Pomerance, C.: On a problem of Oppenheim concerning factorisatio umerorum. J.Number Theory 17, 1–28 (1983)
Coppersmith, D.: Fast Evaluation of Logarithms in Fields of Characteristic Two. IEEE Transactions on Information Theory IT 30, 587–594 (1984)
Coppersmith, D.: Modifications to the Number Field Sieve. J. Cryptology 6, 169–180 (1993)
Coppersmith, D., Odlyzko, A., Schroeppel, R.: Discrete logarithms in GF(p). Algorithmica 1, 1–15 (1986)
Gordon, D.: Discrete logarithms in GF(p) using the number field sieve. SIAM Journal of Discrete Mathematics 6, 124–138 (1993)
Joux, A., Lercier, R.: Improvements to the general Number Field Sieve for discrete logarithms in prime fields. Mathematics of Computation 72, 953–967 (2003)
Joux, A., Lercier, R.: Calcul de logarithmes discrets dans GF(p) — 130 chiffres. In: CRYPTO Mailing List (June 2005)
Lenstra, A., Lenstra, H. (eds.): The Development of the Number Field Sieve. Lecture Notes in Mathematics, vol. 1554. Springer, Heidelberg (1993)
Lenstra, H.: Factoring integers with elliptic curves. Annals of Mathematics 126, 649–673 (1987)
Matyukhin, D.: On asymptotic complexity of computing discrete logarithms over GF(p). Discrete Mathematics and Applications 13, 27–50 (2003)
McCurley, K.: The discrete logarithm problem. In: Pomerance, C. (ed.) Cryptography and Computational Number Theory. Proc. Symp.Appl.Math., vol. 42, Amer. Math. Soc (1990)
Odlyzko, A.: Discrete logarithms: The past and the future. Designs, Codes and Cryptography 19, 129–145 (2000)
Odlyzko, A.: Discrete Logarithms and Smooth Polynomials. In: Mullen, G., Shiue, P. (eds.) Finite Fields: Theory, Applications and Algorithms. Contemporary Math, vol. 168, pp. 269–278. Amer. Math. Soc (1994)
Odlyzko, A.M.: Discrete logarithms in finite fields and their cryptographic significance. In: Beth, T., Cot, N., Ingemarsson, I. (eds.) EUROCRYPT 1984. LNCS, vol. 209, pp. 224–314. Springer, Heidelberg (1985)
Odlyzko, A.: On the complexity of Computing Discrete Logarithms and Factoring Integers. In: Cover, T., Gopinath, B. (eds.) Open Problems in Communication and Computation, pp. 113–116. Springer, Heidelberg (1987)
Pollard, J.: Monte Carlo methods for index computations mod p. Mathematics of Computation 32, 918–924 (1978)
Pollard, J.: Factoring with cubic integers. In: [8], pp. 4–10. Springer, Heidelberg (1993)
Pomerance, C.: Fast, rigorous factorization and discrete logarithm algorithms. In: Nozaki, N., Johnson, D., Nishizaki, T., Wilf, H. (eds.) Discrete Algorithms and Complexity, pp. 119–143. Academic Press, London (1987)
Schirokauer, O.: Discrete logarithms and local units. Philosophical Transactions of the Royal Society of London (A) 345, 409–423 (1993)
Schirokauer, O.: Virtual Logarithms. Journal of Algorithms 57, 140–147 (2005)
Semaev, I.: Special prime numbers and discrete logs in prime finite fields. Mathematics of Computation 71, 363–377 (2002)
Shoup, V.: Searching for primitive roots in finite fields. Mathematics of Computation 58, 918–924 (1992)
van Oorschot, P., Wiener, M.: Parallel collision search with cryptanalytic applications. J. Cryptology 12, 1–28 (1999)
Wiedemann, D.: Solving sparse linear equations over finite fields. IEEE Trans.Inform. Theory 32, 54–62 (1986)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Commeine, A., Semaev, I. (2006). An Algorithm to Solve the Discrete Logarithm Problem with the Number Field Sieve. In: Yung, M., Dodis, Y., Kiayias, A., Malkin, T. (eds) Public Key Cryptography - PKC 2006. PKC 2006. Lecture Notes in Computer Science, vol 3958. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11745853_12
Download citation
DOI: https://doi.org/10.1007/11745853_12
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-33851-2
Online ISBN: 978-3-540-33852-9
eBook Packages: Computer ScienceComputer Science (R0)