Available in electronic format
Available in print format		 Mathematics of Computation
Journal of the American Mathematical Society
ISSN 1088-6842(e) ISSN 0025-5718(p)
Previous issue | Table of contents | Next issue
Articles in press | Recently posted articles | Most recent issue | All issues
Previous Article | Next Article
     

Using number fields to compute logarithms in finite fields

Author(s): Oliver Schirokauer.
Journal: Math. Comp. 69 (2000), 1267-1283.
MSC (1991): Primary 11Y40, 11Y16; Secondary 11T71
Posted: May 24, 1999
Retrieve article in: PDF DVI PostScript
This article is available free of charge

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:

[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 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: 10.1090/S0025-5718-99-01137-0
PII: S 0025-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
Posted: May 24, 1999
Copyright of article: Copyright 2000, American Mathematical Society

  AMS Website Logo Small Comments: webmaster@ams.org
© Copyright 2008, American Mathematical Society
Privacy Statement 		Search the AMSPowered by Google