Fast computation of a rational point of a variety over a finite field

Cafure, Antonio; Matera, Guillermo

doi:10.1090/S0025-5718-06-01878-3

Fast computation of a rational point of a variety over a finite field
HTML articles powered by AMS MathViewer

by Antonio Cafure and Guillermo Matera;

Math. Comp. 75 (2006), 2049-2085

DOI: https://doi.org/10.1090/S0025-5718-06-01878-3

Published electronically: July 20, 2006

PDF | Request permission

Abstract:

We exhibit a probabilistic algorithm which computes a rational point of an absolutely irreducible variety over a finite field defined by a reduced regular sequence. Its time-space complexity is roughly quadratic in the logarithm of the cardinality of the field and a geometric invariant of the input system. This invariant, called the degree, is bounded by the Bézout number of the system. Our algorithm works for fields of any characteristic, but requires the cardinality of the field to be greater than a quantity which is roughly the fourth power of the degree of the input variety.

References

M.-E. Alonso, E. Becker, M.-F. Roy, and T. Wörmann, Zeros, multiplicities, and idempotents for zero-dimensional systems, Algorithms in algebraic geometry and applications (Santander, 1994) Progr. Math., vol. 143, Birkhäuser, Basel, 1996, pp. 1–15. MR 1414442, DOI 10.1007/978-3-0348-9104-2_{1}
B. Bank, M. Giusti, J. Heintz, and G. M. Mbakop, Polar varieties, real equation solving, and data structures: the hypersurface case, J. Complexity 13 (1997), no. 1, 5–27. MR 1449757, DOI 10.1006/jcom.1997.0432
B. Bank, M. Giusti, J. Heintz, and G. M. Mbakop, Polar varieties and efficient real elimination, Math. Z. 238 (2001), no. 1, 115–144. MR 1860738, DOI 10.1007/PL00004896
Bernd Bank, Marc Giusti, Joos Heintz, and Luis M. Pardo, Generalized polar varieties and an efficient real elimination procedure, Kybernetika (Prague) 40 (2004), no. 5, 519–550. MR 2120995
B. Bank, M. Giusti, J. Heintz, and L. M. Pardo, Generalized polar varieties: geometry and algorithms, J. Complexity 21 (2005), no. 4, 377–412. MR 2152713, DOI 10.1016/j.jco.2004.10.001
Dario Bini and Victor Y. Pan, Polynomial and matrix computations. Vol. 1, Progress in Theoretical Computer Science, Birkhäuser Boston, Inc., Boston, MA, 1994. Fundamental algorithms. MR 1289412, DOI 10.1007/978-1-4612-0265-3
A. Borodin, Time space tradeoffs (getting closer to the barriers?), 4th International Symposium on Algorithms and Computation, ISAAC ’93, Hong Kong, December 15-17, 1993 (Berlin), Lecture Notes in Comput. Sci., vol. 762, Springer, 1993, pp. 209–220.
Peter Bürgisser, Michael Clausen, and M. Amin Shokrollahi, Algebraic complexity theory, Grundlehren der mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 315, Springer-Verlag, Berlin, 1997. With the collaboration of Thomas Lickteig. MR 1440179, DOI 10.1007/978-3-662-03338-8
A. Cafure and G. Matera, Improved explicit estimates on the number of solutions of equations over a finite field, Finite Fields Appl., 12 (2006), no. 2, 155–185.
D. Castro, M. Giusti, J. Heintz, G. Matera, and L. M. Pardo, The hardness of polynomial equation solving, Found. Comput. Math. 3 (2003), no. 4, 347–420. MR 2009683, DOI 10.1007/s10208-002-0065-7
A.L. Chistov and D.Y. Grigoriev, Subexponential time solving systems of algebraic equations. I, II, LOMI preprints E-9-83, E-10-83, Steklov Institute, Leningrad, 1983.
Nicolas Courtois, Alexander Klimov, Jacques Patarin, and Adi Shamir, Efficient algorithms for solving overdefined systems of multivariate polynomial equations, Advances in cryptology—EUROCRYPT 2000 (Bruges), Lecture Notes in Comput. Sci., vol. 1807, Springer, Berlin, 2000, pp. 392–407. MR 1772028, DOI 10.1007/3-540-45539-6_{2}7
David Cox, John Little, and Donal O’Shea, Ideals, varieties, and algorithms, Undergraduate Texts in Mathematics, Springer-Verlag, New York, 1992. An introduction to computational algebraic geometry and commutative algebra. MR 1189133, DOI 10.1007/978-1-4757-2181-2
David Cox, John Little, and Donal O’Shea, Using algebraic geometry, Graduate Texts in Mathematics, vol. 185, Springer-Verlag, New York, 1998. MR 1639811, DOI 10.1007/978-1-4757-6911-1
Mario de Boer and Ruud Pellikaan, Gröbner bases for codes, Some tapas of computer algebra, Algorithms Comput. Math., vol. 4, Springer, Berlin, 1999, pp. 237–259. MR 1679927, DOI 10.1007/978-3-662-03891-8_{1}0
David Eisenbud, Commutative algebra, Graduate Texts in Mathematics, vol. 150, Springer-Verlag, New York, 1995. With a view toward algebraic geometry. MR 1322960, DOI 10.1007/978-1-4612-5350-1
Jean-Charles Faugère, A new efficient algorithm for computing Gröbner bases without reduction to zero $(F_5)$, Proceedings of the 2002 International Symposium on Symbolic and Algebraic Computation, ACM, New York, 2002, pp. 75–83. MR 2035234, DOI 10.1145/780506.780516
William Fulton, Intersection theory, Ergebnisse der Mathematik und ihrer Grenzgebiete (3) [Results in Mathematics and Related Areas (3)], vol. 2, Springer-Verlag, Berlin, 1984. MR 732620, DOI 10.1007/978-3-662-02421-8
Patrizia Gianni and Teo Mora, Algebraic solution of systems of polynomial equations using Groebner bases, Applied algebra, algebraic algorithms and error-correcting codes (Menorca, 1987) Lecture Notes in Comput. Sci., vol. 356, Springer, Berlin, 1989, pp. 247–257. MR 1008541, DOI 10.1007/3-540-51082-6_{8}3
M. Giusti, J. Heintz, K. Hägele, J. E. Morais, L. M. Pardo, and J. L. Montaña, Lower bounds for Diophantine approximations, J. Pure Appl. Algebra 117/118 (1997), 277–317. Algorithms for algebra (Eindhoven, 1996). MR 1457843, DOI 10.1016/S0022-4049(97)00015-7
M. Giusti, J. Heintz, J. E. Morais, J. Morgenstern, and L. M. Pardo, Straight-line programs in geometric elimination theory, J. Pure Appl. Algebra 124 (1998), no. 1-3, 101–146. MR 1600277, DOI 10.1016/S0022-4049(96)00099-0
M. Giusti, J. Heintz, J. E. Morais, and L. M. Pardo, When polynomial equation systems can be “solved” fast?, Applied algebra, algebraic algorithms and error-correcting codes (Paris, 1995) Lecture Notes in Comput. Sci., vol. 948, Springer, Berlin, 1995, pp. 205–231. MR 1448166, DOI 10.1007/3-540-60114-7_{1}6
Marc Giusti, Joos Heintz, Jose Enrique Morais, and Luis Miguel Pardo, Le rôle des structures de données dans les problèmes d’élimination, C. R. Acad. Sci. Paris Sér. I Math. 325 (1997), no. 11, 1223–1228 (French, with English and French summaries). MR 1490129, DOI 10.1016/S0764-4442(97)83558-6
Marc Giusti, Joos Heintz, and Juan Sabia, On the efficiency of effective Nullstellensätze, Comput. Complexity 3 (1993), no. 1, 56–95. MR 1220078, DOI 10.1007/BF01200407
Marc Giusti, Grégoire Lecerf, and Bruno Salvy, A Gröbner free alternative for polynomial system solving, J. Complexity 17 (2001), no. 1, 154–211. MR 1817612, DOI 10.1006/jcom.2000.0571
Joos Heintz, Definability and fast quantifier elimination in algebraically closed fields, Theoret. Comput. Sci. 24 (1983), no. 3, 239–277. MR 716823, DOI 10.1016/0304-3975(83)90002-6
L. Huguet and A. Poli (eds.), Applied algebra, algebraic algorithms and error-correcting codes, Lecture Notes in Computer Science, vol. 356, Springer-Verlag, Berlin, 1989. MR 1008524, DOI 10.1007/3-540-51082-6
J. Heintz, G. Matera, L. M. Pardo, and R. Wachenchauzer, The intrinsic complexity of parametric elimination methods, Electron. J. SADIO 1 (1998), no. 1, 37–51. MR 1675449
Joos Heintz, Guillermo Matera, and Ariel Waissbein, On the time-space complexity of geometric elimination procedures, Appl. Algebra Engrg. Comm. Comput. 11 (2001), no. 4, 239–296. MR 1818975, DOI 10.1007/s002000000046
Ming-Deh Huang and Yiu-Chung Wong, Solvability of systems of polynomial congruences modulo a large prime, Comput. Complexity 8 (1999), no. 3, 227–257. MR 1737238, DOI 10.1007/s000370050029
Ming-Deh Huang and Yiu-Chung Wong, Extended Hilbert irreducibility and its applications, J. Algorithms 37 (2000), no. 1, 121–145. Ninth Annual ACM-SIAM Symposium on Discrete Algorithms (San Francisco, CA, 1998). MR 1783251, DOI 10.1006/jagm.2000.1098
Erich Kaltofen, Effective Noether irreducibility forms and applications, J. Comput. System Sci. 50 (1995), no. 2, 274–295. 23rd Symposium on the Theory of Computing (New Orleans, LA, 1991). MR 1330258, DOI 10.1006/jcss.1995.1023
Aviad Kipnis and Adi Shamir, Cryptanalysis of the HFE public key cryptosystem by relinearization, Advances in cryptology—CRYPTO ’99 (Santa Barbara, CA), Lecture Notes in Comput. Sci., vol. 1666, Springer, Berlin, 1999, pp. 19–30. MR 1729291, DOI 10.1007/3-540-48405-1_{2}
T. Krick and L. M. Pardo, A computational method for Diophantine approximation, Algorithms in algebraic geometry and applications (Santander, 1994) Progr. Math., vol. 143, Birkhäuser, Basel, 1996, pp. 193–253. MR 1414452
L. Kronecker, Grundzüge einer arithmetischen Theorie der algebraischen Grössen, J. Reine Angew. Math. 92 (1882), 1–122.
Ernst Kunz, Introduction to commutative algebra and algebraic geometry, Birkhäuser Boston, Inc., Boston, MA, 1985. Translated from the German by Michael Ackerman; With a preface by David Mumford. MR 789602
G. Lecerf, Quadratic Newton iteration for systems with multiplicity, Found. Comput. Math. 2 (2002), no. 3, 247–293. MR 1907381, DOI 10.1007/s102080010026
Grégoire Lecerf, Computing the equidimensional decomposition of an algebraic closed set by means of lifting fibers, J. Complexity 19 (2003), no. 4, 564–596. MR 1991984, DOI 10.1016/S0885-064X(03)00031-1
Rudolf Lidl and Harald Niederreiter, Finite fields, Encyclopedia of Mathematics and its Applications, vol. 20, Addison-Wesley Publishing Company, Advanced Book Program, Reading, MA, 1983. With a foreword by P. M. Cohn. MR 746963
Rudolf Lidl and Günter Pilz, Applied abstract algebra, Undergraduate Texts in Mathematics, Springer-Verlag, New York, 1984. MR 765220, DOI 10.1007/978-1-4615-6465-2
F. S. Macaulay, The algebraic theory of modular systems, Cambridge Mathematical Library, Cambridge University Press, Cambridge, 1994. Revised reprint of the 1916 original; With an introduction by Paul Roberts. MR 1281612
Hideyuki Matsumura, Commutative algebra, 2nd ed., Mathematics Lecture Note Series, vol. 56, Benjamin/Cummings Publishing Co., Inc., Reading, MA, 1980. MR 575344
J.E. Morais, Resolución eficaz de sistemas de ecuaciones polinomiales, Ph.D. thesis, Universidad de Cantabria, Santander, Spain, 1997.
David Mumford, Algebraic geometry. I, Classics in Mathematics, Springer-Verlag, Berlin, 1995. Complex projective varieties; Reprint of the 1976 edition. MR 1344216
Luis M. Pardo, How lower and upper complexity bounds meet in elimination theory, Applied algebra, algebraic algorithms and error-correcting codes (Paris, 1995) Lecture Notes in Comput. Sci., vol. 948, Springer, Berlin, 1995, pp. 33–69. MR 1448154, DOI 10.1007/3-540-60114-7_{4}
Fabrice Rouillier, Solving zero-dimensional systems through the rational univariate representation, Appl. Algebra Engrg. Comm. Comput. 9 (1999), no. 5, 433–461. MR 1697179, DOI 10.1007/s002000050114
Pierre Samuel, Méthodes d’algèbre abstraite en géométrie algébrique, Ergebnisse der Mathematik und ihrer Grenzgebiete [Results in Mathematics and Related Areas], Band 4, Springer-Verlag, Berlin-New York, 1967 (French). Seconde édition, corrigée. MR 213347
J.E. Savage, Models of computation. Exploring the power of computing, Addison-Wesley, Reading, Massachussets, 1998.
Wolfgang M. Schmidt, A lower bound for the number of solutions of equations over finite fields, J. Number Theory 6 (1974), 448–480. MR 360598, DOI 10.1016/0022-314X(74)90043-2
Wolfgang M. Schmidt, Equations over finite fields. An elementary approach, Lecture Notes in Mathematics, Vol. 536, Springer-Verlag, Berlin-New York, 1976. MR 429733, DOI 10.1007/BFb0080437
Éric Schost, Computing parametric geometric resolutions, Appl. Algebra Engrg. Comm. Comput. 13 (2003), no. 5, 349–393. MR 1959170, DOI 10.1007/s00200-002-0109-x
J. T. Schwartz, Fast probabilistic algorithms for verification of polynomial identities, J. Assoc. Comput. Mach. 27 (1980), no. 4, 701–717. MR 594695, DOI 10.1145/322217.322225
I. R. Shafarevich, Basic algebraic geometry, Springer Study Edition, Springer-Verlag, Berlin-New York, 1977. Translated from the Russian by K. A. Hirsch; Revised printing of Grundlehren der mathematischen Wissenschaften, Vol. 213, 1974. MR 447223
Igor R. Shafarevich, Basic algebraic geometry. 1, 2nd ed., Springer-Verlag, Berlin, 1994. Varieties in projective space; Translated from the 1988 Russian edition and with notes by Miles Reid. MR 1328833
Volker Strassen, Algebraic complexity theory, Handbook of theoretical computer science, Vol. A, Elsevier, Amsterdam, 1990, pp. 633–672. MR 1127177
Joachim von zur Gathen, Parallel arithmetic computations: a survey, Mathematical foundations of computer science, 1986 (Bratislava, 1986) Lecture Notes in Comput. Sci., vol. 233, Springer, Berlin, 1986, pp. 93–112. MR 874591, DOI 10.1007/BFb0016236
Joachim von zur Gathen and Jürgen Gerhard, Modern computer algebra, Cambridge University Press, New York, 1999. MR 1689167
Joachim von zur Gathen, Marek Karpinski, and Igor Shparlinski, Counting curves and their projections, Comput. Complexity 6 (1996/97), no. 1, 64–99. MR 1436303, DOI 10.1007/BF01202042
Joachim von zur Gathen, Igor Shparlinski, and Alistair Sinclair, Finding points on curves over finite fields, SIAM J. Comput. 32 (2003), no. 6, 1436–1448. MR 2034245, DOI 10.1137/S0097539799351018
André Weil, Sur les courbes algébriques et les variétés qui s’en déduisent, Publications de l’Institut de Mathématiques de l’Université de Strasbourg [Publications of the Mathematical Institute of the University of Strasbourg], vol. 7, Hermann & Cie, Paris, 1948 (French). Actualités Scientifiques et Industrielles [Current Scientific and Industrial Topics], No. 1041. MR 27151
Oscar Zariski, Algebraic surfaces, Classics in Mathematics, Springer-Verlag, Berlin, 1995. With appendices by S. S. Abhyankar, J. Lipman and D. Mumford; Preface to the appendices by Mumford; Reprint of the second (1971) edition. MR 1336146, DOI 10.1007/978-3-642-61991-5
Richard Zippel, Probabilistic algorithms for sparse polynomials, Symbolic and algebraic computation (EUROSAM ’79, Internat. Sympos., Marseille, 1979) Lecture Notes in Comput. Sci., vol. 72, Springer, Berlin-New York, 1979, pp. 216–226. MR 575692