Changing the ordering of Gröbner bases with LLL: case of two variables

ABSTRACT

We present an algorithm for the transformation of a Gröbner basis of an ideal with respect to any given ordering into a Gröbner basis with respect to any other ordering. This algorithm is based on a modified version of the LLL algorithm. The worst case theoretical complexity of this algorithm is not better than the complexity of the FGLM algorithm; but can also give the theoretical complexity with some parameters depending on the size of the output. When the output is small then algorithm is more efficient. We also present a first implementation of the algorithm in Maple. This algorithm is restricted to the case of two variables but works also in positive dimension.

REFERENCES

• 1: S. Arita. Algorithms for computations in Jacobian group of C_ab curve and their application to discrete-log based public key cryptosystems. IEICE Transactions, J82-A(8):1291--1299, 1999. In Japanese. English translation in the proceedings of the Conference on The Mathematics of Public Key Cryptography, Toronto 1999.
• 2: A. Basiri, A. Enge, J.-C. Faugère, and N. Gürel. Fast arithmetics for superelliptic cubics. Extended version, available from http://www.lix.polytechnique.fr/Labo/Andreas.Enge/vorabdrucke/super.ps, 2002.
• 3: A. Basiri and J.-C. Faugère. Changing the ordering of gröbner bases with LLL: Case of two variables. Technical report, Loria, http://www.inria.fr/rrrt/rr-4746.html, February 2003.
• 4: Eberhard Becker , Teo Mora , Maria Grazia Marinari , Carlo Traverso, The shape of the Shape Lemma, Proceedings of the international symposium on Symbolic and algebraic computation, p.129-133, July 20-22, 1994, Oxford, United Kingdom [doi>10.1145/190347.190382]
• 5: T. Becker and V. Weispfenning. Gröbner bases. Springer-Verlag, NewYork-Berlin-Heidelberg, 1993.
• 6: B. Buchberger. Ein Algorithmus zum Auffinden der Basiselemente des Restklassenringes nach einem nulldimensionalen Polynomideal. PhD thesis, Innsbruck, 1965.
• 7: B. Buchberger. An algorithmical criterion for the solvability of algebraic systems. Aequationes Mathematicae, 4(3):374--383, 1970. (German).
• 8: Bruno Buchberger, A criterion for detecting unnecessary reductions in the construction of Groebner bases, Proceedings of the International Symposiumon on Symbolic and Algebraic Computation, p.3-21, June 01, 1979
• 9: Bruno Buchberger, A note on the complexity of constructing Gröbner-Bases, Proceedings of the European Computer Algebra Conference on Computer Algebra, p.137-145, March 28-30, 1983
• 10: B. Buchberger. Gröbner bases : an algorithmic method in polynomial ideal theory. In R. P. Company, editor, Recent trends in multidimensional system theory, chapter 6, pages 184--232. Bose, 1985.
• 11: D. Cox, J. Little, and D. O'Shea. Ideals, Varieties, and Algorithms. Undergraduate Texts in Mathematics. Springer-Verlag, 1996. second edition.
• 12: J.-C. Faugère. A new efficient algorithm for computing gröbner bases (f4). Journal of Pure and Applied Algebra, 139(1--3):61--88, June 1999.
• 13: J.-C. Faugère. How my computer find all the solutions of cyclic 9. In Lecture Notes Series on Computing, volume 9, pages 1--12. World Scientific Publishing Co., 2001.
• 14: Jean Charles Faugère, A new efficient algorithm for computing Gröbner bases without reduction to zero (F₅), Proceedings of the 2002 international symposium on Symbolic and algebraic computation, p.75-83, July 07-10, 2002, Lille, France [doi>10.1145/780506.780516]
• 15: J.-C. Faugère. Examples for LLL. Technical report, Lip6, http://calfor.lip6.fr/ jcf/Papers/LLL/index.html, April 2003.
• 16: J. C. Faugère , P. Gianni , D. Lazard , T. Mora, Efficient computation of zero-dimensional Gro¨bner bases by change of ordering, Journal of Symbolic Computation, v.16 n.4, p.329-344, Oct. 1993 [doi>10.1006/jsco.1993.1051]
• 17: Ryuichi Harasawa , Joe Suzuki, Fast Jacobian Group Arithmetic on CabCurves, Proceedings of the 4th International Symposium on Algorithmic Number Theory, p.359-376, July 02-07, 2000
• 18: Daniel Lazard, Gröbner-Bases, Gaussian elimination and resolution of systems of algebraic equations, Proceedings of the European Computer Algebra Conference on Computer Algebra, p.146-156, March 28-30, 1983
• 19: D Lazard, Ideal bases and primary decomposition: case of two variables, Journal of Symbolic Computation, v.1 n.3, p.261-270, September 1985 [doi>10.1016/S0747-7171(85)80035-3]
• 20: A. Lenstra, H. Lenstra, and L. Lovász. Factoring polynomials with rational coefficients. Math. Ann., 261:515--534, 1982.
• 21: A. K. Lenstra. Factoring multivariate polynomials over finite fields. J. Computer and System Sciences, 30(2):235--248, 1985.
• 22: K. Mahler. An analogue of minkowski's geometry of numbers in a field of series. In Annals of Math, volume 42, pages 488--522, 1941.
• 23: Sachar Paulus, Lattice Basis Reduction in Function Fields, Proceedings of the Third International Symposium on Algorithmic Number Theory, p.567-575, June 21-25, 1998

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Computations on polynomials

General Terms:
Algorithms

Keywords:
Gröbner basis, LLL, complexity, reduced lattice basis