Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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

 
 

 

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.


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

  • 1. M.E. Alonso, E. Becker, M.-F. Roy, and T. Wörmann, Zeroes, multiplicities and idempotents for zerodimensional systems, Algorithms in Algebraic Geometry and Applications, Proceedings of MEGA'94 (Boston), Progr. Math., vol. 143, Birkhäuser, Boston, 1996, pp. 1-15. MR 1414442 (97i:13027)
  • 2. B. Bank, M. Giusti, J. Heintz, and G.M. Mbakop, Polar varieties and efficient real equation solving: The hypersurface case, J. Complexity 13 (1997), no. 1, 5-27. MR 1449757 (98h:68123)
  • 3. -, Polar varieties and efficient real elimination, Math. Z. 238 (2001), no. 1, 115-144. MR 1860738 (2002g:14084)
  • 4. B. Bank, M. Giusti, J. Heintz, and L.M. Pardo, A first approach to generalized polar varieties, Kybernetika (Prague) 40 (2004), no. 5, 519-550. MR 2120995 (2006e:14078)
  • 5. -, Generalized polar varieties: Geometry and algorithms, J. Complexity 21 (2005), no. 4, 377-412. MR 2152713
  • 6. D. Bini and V. Pan, Polynomial and matrix computations, Progress in Theoretical Computer Science, Birkhäuser, Boston, 1994. MR 1289412 (95k:65003)
  • 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. P. Bürgisser, M. Clausen, and M.A. Shokrollahi, Algebraic complexity theory, Grundlehren Math. Wiss., vol. 315, Springer, Berlin, 1997. MR 1440179 (99c:68002)
  • 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 (2004k:68056)
  • 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. N. Courtois, A. Klimov, J. Patarin, and A. Shamir, Efficient algorithms for solving overdefined systems of multivariate polynomial equations, EUROCRYPT 2000 (Berlin) (B. Preneel, ed.), Lecture Notes in Comput. Sci., vol. 1807, Springer, 2000, pp. 71-79. MR 1772028
  • 13. D. Cox, J. Little, and D. O'Shea, Ideals, varieties, and algorithms: an introduction to computational algebraic geometry and commutative algebra, Undergrad. Texts Math., Springer, New York, 1992. MR 1189133 (93j:13031)
  • 14. -, Using algebraic geometry, Grad. Texts in Math., vol. 185, Springer, New York, 1998. MR 1639811 (99h:13033)
  • 15. M. de Boer and R. Pellikaan, Gröbner bases for codes, Some tapas in computer algebra (A. Cohen et al., ed.), Algorithms Comput. Math., vol. 4, Springer, Berlin, 1999, pp. 237-259. MR 1679927 (2000d:94029a)
  • 16. D. Eisenbud, Commutative algebra with a view toward algebraic geometry, Grad. Texts in Math., vol. 150, Springer, New York, 1995. MR 1322960 (97a:13001)
  • 17. J.-C. Faugère, A new efficient algorithm for computing Gröbner bases without reduction to zero (F5), ISSAC'02: Proceedings of the International Symposium on Symbolic and Algebraic Computation, Lille, France, July 7-10, 2002 (New York) (T. Mora, ed.), ACM Press, 2002, pp. 75-83. MR 2035234 (2005c:13033)
  • 18. W. Fulton, Intersection Theory, Springer, Berlin, Heidelberg, New York, 1984.MR 0732620 (85k:14004)
  • 19. P. Gianni and T. Mora, Algebraic solution of systems of polynomial equations using Gröbner bases, Proceedings 5th International Symposium on Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, AAECC-5, Menorca, Spain, June 15-19, 1987 (Berlin) (L. Huguet and A. Poli, eds.), Lecture Notes in Comput. Sci., vol. 356, Springer, 1989, pp. 247-257. MR 1008541 (91e:13024)
  • 20. M. Giusti, K. Hägele, J. Heintz, J.E. Morais, J.L. Montaña, and L.M. Pardo, Lower bounds for Diophantine approximation, J. Pure Appl. Algebra 117, 118 (1997), 277-317. MR 1457843 (99d:68106)
  • 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), 101-146. MR 1600277 (99d:68128)
  • 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, Proceedings AAECC-11 (Berlin) (G. Cohen, M. Giusti, and T. Mora, eds.), Lecture Notes in Comput. Sci., vol. 948, Springer, 1995, pp. 205-231. MR 1448166 (98a:68106)
  • 23. -, Le rôle des structures de données dans les problèmes d'élimination, C. R. Math. Acad. Sci. Paris 325 (1997), 1223-1228.MR 1490129 (98j:68068)
  • 24. M. Giusti, J. Heintz, and J. Sabia, On the efficiency of effective Nullstellensätze, Comput. Complexity 3 (1993), 56-95.MR 1220078 (94i:13016)
  • 25. M. Giusti, G. Lecerf, and B. Salvy, A Gröbner free alternative for polynomial system solving, J. Complexity 17 (2001), no. 1, 154-211.MR 1817612 (2002b:68123)
  • 26. J. Heintz, Definability and fast quantifier elimination in algebraically closed fields, Theoret. Comput. Sci. 24 (1983), no. 3, 239-277.MR 0716823 (85a:68062)
  • 27. -, On the computational complexity of polynomials and bilinear mappings. A survey, Proceedings 5th International Symposium on Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, AAECC-5, Menorca, Spain, June 15-19, 1987 (Berlin) (L. Huguet and A. Poli, eds.), Lecture Notes in Comput. Sci., vol. 356, Springer, 1989, pp. 269-300. MR 1008524 (90d:94001)
  • 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 (2000b:65249)
  • 29. J. Heintz, G. Matera, and A. Waissbein, On the time-space complexity of geometric elimination procedures, Appl. Algebra Engrg. Comm. Comput. 11 (2001), no. 4, 239-296. MR 1818975 (2002c:68108)
  • 30. M.-D. Huang and Y.-C. Wong, Solvability of systems of polynomial congruences modulo a large prime, Comput. Complexity 8 (1999), no. 3, 227-257.MR 1737238 (2000j:11044)
  • 31. -, Extended Hilbert irreducibility and its applications, J. Algorithms 37 (2000), no. 1, 121-145. MR 1783251 (2001h:12002)
  • 32. E. Kaltofen, Effective Noether irreducibility forms and applications, J. Comput. System Sci. 50 (1995), no. 2, 274-295.MR 1330258 (96g:68053)
  • 33. A. Kipnis and A. Shamir, Cryptanalysis of the HFE PublicKeyCryptosystem by relinearization, Proceedings of Advances in Cryptology - CRYPTO'99, Santa Barbara, California, USA, August 15-19, 1999 (Berlin) (M.J. Wiener, ed.), Lecture Notes in Comput. Sci., vol. 1666, Springer, 1999, pp. 19-30.MR 1729291 (2000i:94052)
  • 34. T. Krick and L.M. Pardo, A computational method for Diophantine approximation, Algorithms in Algebraic Geometry and Applications, Proceedings of MEGA'94 (Boston) (L. González-Vega and T. Recio, eds.), Progr. Math., vol. 143, Birkhäuser Boston, 1996, pp. 193-254. MR 1414452 (98h:13039)
  • 35. L. Kronecker, Grundzüge einer arithmetischen Theorie der algebraischen Grössen, J. Reine Angew. Math. 92 (1882), 1-122.
  • 36. E. Kunz, Introduction to commutative algebra and algebraic geometry, Birkhäuser, Boston, 1985. MR 0789602 (86e:14001)
  • 37. G. Lecerf, Quadratic Newton iteration for systems with multiplicity, Found. Comput. Math. 2 (2002), no. 3, 247-293. MR 1907381 (2003f:65090)
  • 38. -, Computing the equidimensional decomposition of an algebraic closed set by means of lifting fibers, J. Complexity 19 (2003), no. 4, 564-596. MR 1991984 (2004j:68200)
  • 39. R. Lidl and H. Niederreiter, Finite fields, Addison-Wesley, Reading, Massachusetts, 1983. MR 0746963 (86c:11106)
  • 40. R. Lidl and G. Pilz, Applied abstract algebra, Undergrad. Texts Math., Springer, New York, 1984. MR 0765220 (86d:00002)
  • 41. F. S. Macaulay, The algebraic theory of modular systems, Cambridge Univ. Press, Cambridge, 1916. MR 1281612 (95i:13001)
  • 42. H. Matsumura, Commutative algebra, Benjamin, 1980. MR 0575344 (82i:13003)
  • 43. J.E. Morais, Resolución eficaz de sistemas de ecuaciones polinomiales, Ph.D. thesis, Universidad de Cantabria, Santander, Spain, 1997.
  • 44. D. Mumford, Algebraic geometry I. Complex projective varieties, 2nd ed., Classics Math., Springer, Berlin, 1995. MR 1344216 (96d:14001)
  • 45. L.M. Pardo, How lower and upper complexity bounds meet in elimination theory, Applied Algebra, Algebraic Algorithms and Error Correcting Codes, Proceedings of AAECC-11 (Berlin) (G. Cohen, M. Giusti, and T. Mora, eds.), Lecture Notes in Comput. Sci., vol. 948, Springer, 1995, pp. 33-69.MR 1448154 (99a:68097)
  • 46. F. Rouillier, Solving zero-dimensional systems through rational univariate representation, Appl. Algebra Engrg. Comm. Comput. 9 (1997), no. 5, 433-461.MR 1697179 (2000e:13038)
  • 47. P. Samuel, Méthodes d'algèbre abstraite en géométrie algébrique, Springer, Berlin, Heidelberg, New York, 1967. MR 0213347 (35:4211)
  • 48. J.E. Savage, Models of computation. Exploring the power of computing, Addison-Wesley, Reading, Massachussets, 1998.
  • 49. W. Schmidt, A lower bound for the number of solutions of equations over finite fields, J. Number Theory 6 (1974), no. 6, 448-480. MR 0360598 (50:13045)
  • 50. -, Equations over finite fields. An elementary approach, Lectures Notes in Math., no. 536, Springer, New York, 1976.MR 0429733 (55:2744)
  • 51. E. Schost, Computing parametric geometric resolutions, Appl. Algebra Engrg. Comm. Comput. 13 (2003), 349-393. MR 1959170 (2003k:13035)
  • 52. J.T. Schwartz, Fast probabilistic algorithms for verification of polynomial identities, J. ACM 27 (1980), no. 4, 701-717.MR 0594695 (82m:68078)
  • 53. I.R. Shafarevich, Basic algebraic geometry, Grad. Texts in Math., Springer, New York, 1984. MR 0447223 (56:5538)
  • 54. -, Basic algebraic geometry: Varieties in projective space, Springer, Berlin, Heidelberg, New York, 1994. MR 1328833 (95m:14001)
  • 55. V. Strassen, Algebraic complexity theory, Handbook of Theoretical Computer Science (J. van Leeuwen, ed.), Elsevier, Amsterdam, 1990, pp. 634-671.MR 1127177
  • 56. J. von zur Gathen, Parallel arithmetic computations: a survey, Proceedings of the 12th International Symposium on Mathematical Foundations of Computer Science, Bratislava, Czechoslovakia, August 25-29, 1996 (Berlin) (J. Gruska, B. Rovan, and J. Wiedermann, eds.), Lecture Notes in Comput. Sci., vol. 233, Springer, August 1986, pp. 93-112. MR 0874591
  • 57. J. von zur Gathen and J. Gerhard, Modern computer algebra, Cambridge Univ. Press, Cambridge, 1999. MR 1689167 (2000j:68205)
  • 58. J. von zur Gathen, M. Karpinski, and I. Shparlinski, Counting curves and their projections, Comput. Complexity 6 (1997), no. 3, 64-99.MR 1436303 (98d:68111)
  • 59. J. von zur Gathen, I. Shparlinski, and A. Sinclair, Finding points on curves over finite fields, SIAM J. Comput. 32 (2003), no. 6, 1436-1448.MR 2034245 (2005b:68293)
  • 60. A. Weil, Sur les courbes algébriques et les varietés qui s'en déduisent, Hermann, Paris, 1948.MR 0027151 (10:262c)
  • 61. O. Zariski, Algebraic surfaces, Classics Math., Springer, Berlin, 1995.MR 1336146 (96c:14024)
  • 62. R. Zippel, Probabilistic algorithms for sparse polynomials, EUROSAM '79: Proceedings of International Symposium on Symbolic and Algebraic Computation, Marseille 1979 (Berlin), Lecture Notes in Comput. Sci., vol. 72, Springer, 1979, pp. 216-226.MR 0575692 (81g:68061)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2000): 11G25, 14G05, 68W30, 11G20, 13P05, 68Q10, 68Q25

Retrieve articles in all journals with MSC (2000): 11G25, 14G05, 68W30, 11G20, 13P05, 68Q10, 68Q25


Additional Information

Antonio Cafure
Affiliation: Departamento de Matemática, Facultad de Ciencias Exactas y Naturales, Universidad de Buenos Aires, Ciudad Universitaria, Pabellón I (1428) Buenos Aires, Argentina
Email: acafure@dm.uba.ar

Guillermo Matera
Affiliation: Instituto del Desarrollo Humano, Universidad Nacional de General Sarmiento, J.M. Gutiérrez 1150 (1613) Los Polvorines, Buenos Aires, Argentina; and National Council of Science and Technology (CONICET), Argentina
Email: gmatera@ungs.edu.ar

DOI: https://doi.org/10.1090/S0025-5718-06-01878-3
Keywords: Varieties over finite fields, rational points, geometric solutions, straight-line programs, probabilistic algorithms, first Bertini theorem.
Received by editor(s): December 10, 2003
Received by editor(s) in revised form: October 10, 2005
Published electronically: July 20, 2006
Additional Notes: This research was partially supported by the following grants: UBACyT X112, PIP CONICET 2461, and UNGS 30/3005
Dedicated: Dedicated to Joos Heintz on the occasion of his 60th birthday
Article copyright: © Copyright 2006 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.

American Mathematical Society