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

Authors: Antonio Cafure and Guillermo Matera
Journal: Math. Comp. 75 (2006), 2049-2085
MSC (2000): Primary 11G25, 14G05, 68W30; Secondary 11G20, 13P05, 68Q10, 68Q25
DOI: https://doi.org/10.1090/S0025-5718-06-01878-3
Published electronically: July 20, 2006
MathSciNet review: 2240649
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

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.

1. 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, https://doi.org/10.1007/978-3-0348-9104-2_1
2. 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, https://doi.org/10.1006/jcom.1997.0432
3. 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, https://doi.org/10.1007/PL00004896
4. 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
5. 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, https://doi.org/10.1016/j.jco.2004.10.001
6. 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
7. 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.
8. 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
9. 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.
10. 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, https://doi.org/10.1007/s10208-002-0065-7
11. 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.
12. 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, https://doi.org/10.1007/3-540-45539-6_27
13. 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
14. David Cox, John Little, and Donal O’Shea, Using algebraic geometry, Graduate Texts in Mathematics, vol. 185, Springer-Verlag, New York, 1998. MR 1639811
15. 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, https://doi.org/10.1007/978-3-662-03891-8_10
16. David Eisenbud, Commutative algebra, Graduate Texts in Mathematics, vol. 150, Springer-Verlag, New York, 1995. With a view toward algebraic geometry. MR 1322960
17. Jean-Charles Faugère, A new efficient algorithm for computing Gröbner bases without reduction to zero (𝐹₅), Proceedings of the 2002 International Symposium on Symbolic and Algebraic Computation, ACM, New York, 2002, pp. 75–83. MR 2035234, https://doi.org/10.1145/780506.780516
18. 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
19. 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, https://doi.org/10.1007/3-540-51082-6_83
20. 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, https://doi.org/10.1016/S0022-4049(97)00015-7
21. 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, https://doi.org/10.1016/S0022-4049(96)00099-0
22. 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, https://doi.org/10.1007/3-540-60114-7_16
23. 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, https://doi.org/10.1016/S0764-4442(97)83558-6
24. Marc Giusti, Joos Heintz, and Juan Sabia, On the efficiency of effective Nullstellensätze, Comput. Complexity 3 (1993), no. 1, 56–95. MR 1220078, https://doi.org/10.1007/BF01200407
25. 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, https://doi.org/10.1006/jcom.2000.0571
26. Joos Heintz, Definability and fast quantifier elimination in algebraically closed fields, Theoret. Comput. Sci. 24 (1983), no. 3, 239–277. MR 716823, https://doi.org/10.1016/0304-3975(83)90002-6
27. 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
28. 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
29. 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, https://doi.org/10.1007/s002000000046
30. 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, https://doi.org/10.1007/s000370050029
31. 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, https://doi.org/10.1006/jagm.2000.1098
32. 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, https://doi.org/10.1006/jcss.1995.1023
33. 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, https://doi.org/10.1007/3-540-48405-1_2
34. 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
35. L. Kronecker, Grundzüge einer arithmetischen Theorie der algebraischen Grössen, J. Reine Angew. Math. 92 (1882), 1-122.
36. 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
37. G. Lecerf, Quadratic Newton iteration for systems with multiplicity, Found. Comput. Math. 2 (2002), no. 3, 247–293. MR 1907381, https://doi.org/10.1007/s102080010026
38. 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, https://doi.org/10.1016/S0885-064X(03)00031-1
39. 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
40. Rudolf Lidl and Günter Pilz, Applied abstract algebra, Undergraduate Texts in Mathematics, Springer-Verlag, New York, 1984. MR 765220
41. 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
42. Hideyuki Matsumura, Commutative algebra, 2nd ed., Mathematics Lecture Note Series, vol. 56, Benjamin/Cummings Publishing Co., Inc., Reading, Mass., 1980. MR 575344
43. J.E. Morais, Resolución eficaz de sistemas de ecuaciones polinomiales, Ph.D. thesis, Universidad de Cantabria, Santander, Spain, 1997.
44. David Mumford, Algebraic geometry. I, Classics in Mathematics, Springer-Verlag, Berlin, 1995. Complex projective varieties; Reprint of the 1976 edition. MR 1344216
45. 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, https://doi.org/10.1007/3-540-60114-7_4
46. Fabrice Rouillier, Solving zero-dimensional systems through the rational univariate representation, Appl. Algebra Engrg. Comm. Comput. 9 (1999), no. 5, 433–461. MR 1697179, https://doi.org/10.1007/s002000050114
47. Pierre Samuel, Méthodes d’algèbre abstraite en géométrie algébrique, Seconde édition, corrigée. Ergebnisse der Mathematik und ihrer Grenzgebiete, Band 4, Springer-Verlag, Berlin-New York, 1967 (French). MR 0213347
48. J.E. Savage, Models of computation. Exploring the power of computing, Addison-Wesley, Reading, Massachussets, 1998.
49. 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, https://doi.org/10.1016/0022-314X(74)90043-2
50. Wolfgang M. Schmidt, Equations over finite fields. An elementary approach, Lecture Notes in Mathematics, Vol. 536, Springer-Verlag, Berlin-New York, 1976. MR 0429733
51. Éric Schost, Computing parametric geometric resolutions, Appl. Algebra Engrg. Comm. Comput. 13 (2003), no. 5, 349–393. MR 1959170, https://doi.org/10.1007/s00200-002-0109-x
52. J. T. Schwartz, Fast probabilistic algorithms for verification of polynomial identities, J. Assoc. Comput. Mach. 27 (1980), no. 4, 701–717. MR 594695, https://doi.org/10.1145/322217.322225
53. 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 0447223
54. 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
55. Volker Strassen, Algebraic complexity theory, Handbook of theoretical computer science, Vol. A, Elsevier, Amsterdam, 1990, pp. 633–672. MR 1127177
56. 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, https://doi.org/10.1007/BFb0016236
57. Joachim von zur Gathen and Jürgen Gerhard, Modern computer algebra, Cambridge University Press, New York, 1999. MR 1689167
58. 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, https://doi.org/10.1007/BF01202042
59. 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, https://doi.org/10.1137/S0097539799351018
60. André Weil, Sur les courbes algébriques et les variétés qui s’en déduisent, Actualités Sci. Ind., no. 1041 = Publ. Inst. Math. Univ. Strasbourg 7 (1945), Hermann et Cie., Paris, 1948 (French). MR 0027151
61. 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
62. 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