Using number fields to compute logarithms in finite fields

Schirokauer, Oliver

doi:10.1090/S0025-5718-99-01137-0

Using number fields to compute logarithms in finite fields
HTML articles powered by AMS MathViewer

by Oliver Schirokauer PDF

Math. Comp. 69 (2000), 1267-1283 Request permission

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

Leonard M. Adleman, The function field sieve, Algorithmic number theory (Ithaca, NY, 1994) Lecture Notes in Comput. Sci., vol. 877, Springer, Berlin, 1994, pp. 108–121. MR 1322716, DOI 10.1007/3-540-58691-1_{4}8
Leonard M. Adleman and Jonathan DeMarrais, A subexponential algorithm for discrete logarithms over all finite fields, Math. Comp. 61 (1993), no. 203, 1–15. MR 1225541, DOI 10.1090/S0025-5718-1993-1225541-3
L.M. Adleman, M.-D. Huang, Function field method for discrete logarithms over finite fields, preprint (1998).
Eric Bach and Jeffrey Shallit, Factoring with cyclotomic polynomials, Math. Comp. 52 (1989), no. 185, 201–219. MR 947467, DOI 10.1090/S0025-5718-1989-0947467-1
Johannes Buchmann and Victor Shoup, Constructing nonresidues in finite fields and the extended Riemann hypothesis, Math. Comp. 65 (1996), no. 215, 1311–1326. MR 1348040, DOI 10.1090/S0025-5718-96-00751-X
A. K. Lenstra and H. W. Lenstra Jr. (eds.), The development of the number field sieve, Lecture Notes in Mathematics, vol. 1554, Springer-Verlag, Berlin, 1993. MR 1321216, DOI 10.1007/BFb0091534
E. R. Canfield, Paul Erdős, and Carl Pomerance, On a problem of Oppenheim concerning “factorisatio numerorum”, J. Number Theory 17 (1983), no. 1, 1–28. MR 712964, DOI 10.1016/0022-314X(83)90002-1
Henri Cohen, A course in computational algebraic number theory, Graduate Texts in Mathematics, vol. 138, Springer-Verlag, Berlin, 1993. MR 1228206, DOI 10.1007/978-3-662-02945-9
Don Coppersmith, Modifications to the number field sieve, J. Cryptology 6 (1993), no. 3, 169–180. MR 1233462, DOI 10.1007/BF00198464
T. Denny,, A Lanczos implementation for $GF(p)$, Universität des Saarlandes, to appear.
Taher ElGamal, A subexponential-time algorithm for computing discrete logarithms over $\textrm {GF}(p^2)$, IEEE Trans. Inform. Theory 31 (1985), no. 4, 473–481. MR 798553, DOI 10.1109/TIT.1985.1057075
Daniel M. Gordon, Discrete logarithms in $\textrm {GF}(p)$ using the number field sieve, SIAM J. Discrete Math. 6 (1993), no. 1, 124–138. MR 1201995, DOI 10.1137/0406010
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.
M. Kraitchik, Théorie des nombres, Vol. 1, Gauthier-Villars, Paris, 1922.
M. Kraitchik, Recherches sur la théorie des nombres, Gauthier-Villars, Paris, 1924.
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.
Serge Lang, Algebraic number theory, Addison-Wesley Publishing Co., Inc., Reading, Mass.-London-Don Mills, Ont., 1970. MR 0282947
A. K. Lenstra and H. W. Lenstra Jr. (eds.), The development of the number field sieve, Lecture Notes in Mathematics, vol. 1554, Springer-Verlag, Berlin, 1993. MR 1321216, DOI 10.1007/BFb0091534
A. K. Lenstra, H. W. Lenstra Jr., and L. Lovász, Factoring polynomials with rational coefficients, Math. Ann. 261 (1982), no. 4, 515–534. MR 682664, DOI 10.1007/BF01457454
A. K. Lenstra and H. W. Lenstra Jr. (eds.), The development of the number field sieve, Lecture Notes in Mathematics, vol. 1554, Springer-Verlag, Berlin, 1993. MR 1321216, DOI 10.1007/BFb0091534
S. Minakshi Sundaram, On non-linear partial differential equations of the hyperbolic type, Proc. Indian Acad. Sci., Sect. A. 9 (1939), 495–503. MR 0000089
H. W. Lenstra Jr., Algorithms for finite fields, Number theory and cryptography (Sydney, 1989) London Math. Soc. Lecture Note Ser., vol. 154, Cambridge Univ. Press, Cambridge, 1990, pp. 76–85. MR 1055400
H. W. Lenstra Jr., Algorithms in algebraic number theory, Bull. Amer. Math. Soc. (N.S.) 26 (1992), no. 2, 211–244. MR 1129315, DOI 10.1090/S0273-0979-1992-00284-7
R. Lovorn-Bender, Rigorous, subexponential discrete logarithms in $GF(p^{2})$, Siam J. Discrete Math. (to appear).
Kevin S. McCurley, The discrete logarithm problem, Cryptology and computational number theory (Boulder, CO, 1989) Proc. Sympos. Appl. Math., vol. 42, Amer. Math. Soc., Providence, RI, 1990, pp. 49–74. MR 1095551, DOI 10.1090/psapm/042/1095551
Alfred J. Menezes, Tatsuaki Okamoto, and Scott A. Vanstone, Reducing elliptic curve logarithms to logarithms in a finite field, IEEE Trans. Inform. Theory 39 (1993), no. 5, 1639–1646. MR 1281712, DOI 10.1109/18.259647
A. K. Lenstra and H. W. Lenstra Jr. (eds.), The development of the number field sieve, Lecture Notes in Mathematics, vol. 1554, Springer-Verlag, Berlin, 1993. MR 1321216, DOI 10.1007/BFb0091534
Carl Pomerance, The role of smooth numbers in number-theoretic algorithms, Proceedings of the International Congress of Mathematicians, Vol. 1, 2 (Zürich, 1994) Birkhäuser, Basel, 1995, pp. 411–422. MR 1403941
Oliver Schirokauer, Discrete logarithms and local units, Philos. Trans. Roy. Soc. London Ser. A 345 (1993), no. 1676, 409–423. MR 1253502, DOI 10.1098/rsta.1993.0139
O. Schirokauer, Determing the gap between the function field sieve and the number field sieve, in preparation.
Oliver Schirokauer, Damian Weber, and Thomas Denny, Discrete logarithms: the effectiveness of the index calculus method, Algorithmic number theory (Talence, 1996) Lecture Notes in Comput. Sci., vol. 1122, Springer, Berlin, 1996, pp. 337–361. MR 1446523, DOI 10.1007/3-540-61581-4_{6}6
Victor Shoup, Searching for primitive roots in finite fields, Math. Comp. 58 (1992), no. 197, 369–380. MR 1106981, DOI 10.1090/S0025-5718-1992-1106981-9
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.
Damian Weber, Computing discrete logarithms with the general number field sieve, Algorithmic number theory (Talence, 1996) Lecture Notes in Comput. Sci., vol. 1122, Springer, Berlin, 1996, pp. 391–403. MR 1446527, DOI 10.1007/3-540-61581-4_{7}0
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.
Douglas H. Wiedemann, Solving sparse linear equations over finite fields, IEEE Trans. Inform. Theory 32 (1986), no. 1, 54–62. MR 831560, DOI 10.1109/TIT.1986.1057137