Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

 
 

 

Using number fields
to compute logarithms in finite fields


Author: Oliver Schirokauer
Journal: Math. Comp. 69 (2000), 1267-1283
MSC (1991): Primary 11Y40, 11Y16; Secondary 11T71
DOI: https://doi.org/10.1090/S0025-5718-99-01137-0
Published electronically: May 24, 1999
MathSciNet review: 1653978
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: We describe an adaptation of the number field sieve to the problem of computing logarithms in a finite field. We conjecture that the running time of the algorithm, when restricted to finite fields of an arbitrary but fixed degree, is $L_{q}[1/3; (64/9)^{1/3}+o(1)],$ where $q$ is the cardinality of the field, $L_{q}[s;c]={\exp }(c(\log q)^{s}(\log \log q)^{1-s}),$ and the $o(1)$ is for $q\to \infty $. The number field sieve factoring algorithm is conjectured to factor a number the size of $q$ in the same amount of time.


References [Enhancements On Off] (What's this?)

  • [1] L.M. Adleman, The function field sieve, Algorithmic number theory, ANTS-I (eds. L.M. Adleman, M.-D. Huang), Lecture Notes in Comput. Sci., vol. 877, Springer-Verlag, Berlin, 1994, pp. 108-121. MR 96d:11135
  • [2] L.M. Adleman, J. DeMarrais, A subexponential algorithm for discrete logarithms over all finite fields, Math. Comp. 161 (1993), 1-15. MR 94e:11140
  • [3] L.M. Adleman, M.-D. Huang, Function field method for discrete logarithms over finite fields, preprint (1998).
  • [4] E. Bach, J. Shallit, Factoring with cyclotomic polynomials, Math. Comp. 52 (1989), 201-219. MR 89k:11127
  • [5] J.A. Buchmann, V. Shoup, Constructing nonresidues in finite fields and the extended Riemann hypothesis, Math. Comp. 65 (1996), 1311-1326. MR 96j:11169
  • [6] J.P. Buhler, H.W. Lenstra, Jr., C. Pomerance, Factoring integers with the number field sieve, The development of the number field sieve (eds. A.K. Lenstra, H.W. Lenstra, Jr.), Lecture Notes in Math., vol. 1554, Springer-Verlag, Berlin, 1993, pp. 50-94. MR 96m:11116
  • [7] E.R. Canfield, P. Erdös, C. Pomerance, On a problem of Oppenheim concerning ``factorisatio numerorum", J. Number Theory 17 (1983), 1-28. MR 85j:11012
  • [8] H. Cohen, A course in computational algebraic number theory, Springer-Verlag, Berlin, 1993. MR 94i:11105
  • [9] D. Coppersmith, Modifications to the number field sieve, J. Cryptology 6 (1993), 169-180. MR 94h:11111
  • [10] T. Denny,, A Lanczos implementation for $GF(p)$, Universität des Saarlandes, to appear.
  • [11] T. ElGamal, A subexponential-time algorithm for computing discrete logarithms over $GF(p^{2})$, IEEE Trans. Inform. Theory 31 (1985), 473-481. MR 86j:11130
  • [12] D. Gordon, Discrete logarithms using the number field sieve, Siam J. Discrete Math. 6 (1993), 124-138. MR 94d:11104
  • [13] D. Gordon, K. McCurley, Massively parallel computation of discrete logarithms, Advances in cryptology - Crypto '92 (ed. E.F. Brickell), Lecture Notes in Comput. Sci., vol. 740, Springer-Verlag, Berlin, 1993, pp. 312-323.
  • [14] M. Kraitchik, Théorie des nombres, Vol. 1, Gauthier-Villars, Paris, 1922.
  • [15] M. Kraitchik, Recherches sur la théorie des nombres, Gauthier-Villars, Paris, 1924.
  • [16] M. LaMacchia, A. Odlyzko, Solving large sparse linear systems over finite fields, Advances in cryptology - Crypto '90 (eds. A.J. Menezes, S.A. Vanstone), Lecture Notes Comput. Sci., vol. 537, 1991, pp. 109-133.
  • [17] S. Lang, Algebraic number theory, Addison-Wesley, Reading, MA, 1970. MR 44:181
  • [18] A.K. Lenstra, H.W. Lenstra, Jr., (eds.), The development of the number field sieve, Lecture Notes in Math., vol. 1554, Springer-Verlag, Berlin, 1993. MR 96m:11116
  • [19] A.K. Lenstra, H.W. Lenstra, Jr., L. Lovász, Factoring polynomials with rational coefficients, Math. Ann. 261 (1982), 515-534. MR 84a:12002
  • [20] A.K Lenstra, H.W. Lenstra, Jr., M.S. Manasse, J.M. Pollard, The number field sieve, The development of the number field sieve (eds. A.K. Lenstra, H.W. Lenstra, Jr.), Lecture Notes in Math., vol. 1554, Springer-Verlag, Berlin, 1993, pp. 11-42. MR 96m:11116
  • [21] H.W. Lenstra, Jr., Factoring integers with elliptic curves, Ann. of Math. 126 (1987), 649-673. MR 89g:11129
  • [22] H.W. Lenstra, Jr., Algorithms for finite fields, Number theory and cryptography (ed. J.H. Loxton), London Math. Soc. Lecture Note Ser., vol. 154, Cambridge Univ. Press, Cambridge, 1990, pp. 76-85. MR 92b:11091
  • [23] H.W. Lenstra, Jr., Algorithms in algebraic number theory, Bull. Amer. Math. Soc. 26 (1992), 211-244. MR 93g:11131
  • [24] R. Lovorn-Bender, Rigorous, subexponential discrete logarithms in $GF(p^{2})$, Siam J. Discrete Math. (to appear).
  • [25] K. McCurley, The discrete logarithm problem, Cryptology and computational number theory (ed. C. Pomerance), Proc. Sympos. Appl. Math., vol. 42, 1990, pp. 49-74. MR 92d:11133
  • [26] A. Menezes, T. Okamoto, S. Vanstone, Reducing elliptic curve logarithms to logarithms in a finite field, IEEE Trans. Inform. Theory 39 (1993), 1639-1646. MR 95e:94038
  • [27] J.M. Pollard, The lattice sieve, The development of the number field sieve (eds. A.K. Lenstra, H.W. Lenstra, Jr.), Lecture Notes in Math., vol. 1554, Springer-Verlag, Berlin, 1993, pp. 43-49. MR 96m:11116
  • [28] C. Pomerance, The role of smooth numbers in number-theoretic algorithms, Proceedings of the International Congress of Mathematicians (Zurich, 1994) (ed. S.D. Chatterji), Birkhäuser, Basel, 1995, pp. 411-422. MR 97m:11156
  • [29] O. Schirokauer, Discrete logarithms and local units, Theory and applications of numbers without large prime factors (ed. R.C. Vaughan), Philos. Trans. Roy. Soc. London Ser. A, vol. 345, The Royal Society, London, 1993, pp. 409-423. MR 95c:11156
  • [30] O. Schirokauer, Determing the gap between the function field sieve and the number field sieve, in preparation.
  • [31] O. Schirokauer, D. Weber, T. Denny, Discrete logarithms - the effectiveness of the index calculus method, Algorithmic number theory, ANTS-II (ed. H. Cohen), Lecture Notes in Comput. Sci., vol. 1122, Springer-Verlag, Berlin, 1996, pp. 337-361. MR 98i:11109
  • [32] V. Shoup, Searching for primitive roots in finite fields, Math. Comp. 58 (1992), 369-380. MR 92e:11140
  • [33] D. Weber, An implementation of the number field sieve to compute discrete logarithms mod $p$, Advances in cryptology - Eurocrypt '95 (eds. L.C. Guillou, J.-J. Quisquater), Lecture Notes in Comput. Sci., vol. 921, Springer-Verlag, Berlin, 1995, pp. 95-105.
  • [34] D. Weber, Computing discrete logarithms with the number field sieve, Algorithmic number theory, ANTS-II (ed. H. Cohen), Lecture Notes in Comput. Sci., vol. 1122, Springer-Verlag, Berlin, 1996, pp. 391-403. MR 98k:11186
  • [35] D. Weber, T. Denny, The solution of McCurley's discrete log challenge, Advances in cryptology - Crypto '98 (ed. H. Krawczyk), Lecture Notes in Comput. Sci., vol. 1462, Springer-Verlag, Berlin, 1998.
  • [36] D. H. Wiedemann, Solving sparse linear equations over finite fields, IEEE Trans. Inform. Theory 32 (1986), 54-62. MR 87g:11166

Similar Articles

Retrieve articles in Mathematics of Computation of the American Mathematical Society with MSC (1991): 11Y40, 11Y16, 11T71

Retrieve articles in all journals with MSC (1991): 11Y40, 11Y16, 11T71


Additional Information

Oliver Schirokauer
Affiliation: Department of Mathematics, Oberlin College, Oberlin, OH 44074
Email: oliver@occs.oberlin.edu

DOI: https://doi.org/10.1090/S0025-5718-99-01137-0
Keywords: Finite field, discrete logarithm, number field sieve
Received by editor(s): July 24, 1997
Received by editor(s) in revised form: July 14, 1998
Published electronically: May 24, 1999
Article copyright: © Copyright 2000 American Mathematical Society

American Mathematical Society