On Decomposition of Tame Polynomials and Rational Functions

  • Jaime Gutierrez
  • David Sevilla
Conference paper
Part of the Lecture Notes in Computer Science book series (LNCS, volume 4194)


In this paper we present algorithmic considerations and theoretical results about the relation between the orders of certain groups associated to the components of a polynomial and the order of the group that corresponds to the polynomial, proving it for arbitrary tame polynomials, and considering the case of rational functions.


Rational Function Polynomial Time Algorithm Computer Algebra Decomposition Algorithm Computer Algebra System 
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.


Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.


  1. 1.
    Alonso, C., Gutierrez, J., Recio, T.: A rational function decomposition algorithm by near-separated polynomials. J. Symbolic Comput. 19(6), 527–544 (1995)zbMATHCrossRefMathSciNetGoogle Scholar
  2. 2.
    Beardon, A.F., Ng, T.W.: On Ritt’s factorization of polynomials. J. London Math. Soc. (2) 62(1), 127–138 (2000)zbMATHCrossRefMathSciNetGoogle Scholar
  3. 3.
    Cade, J.: A new public-key cipher which allows signatures. In: Proc. 2nd SIAM Conf. on Appl. Linear Algebra, Raleigh NC (1985)Google Scholar
  4. 4.
    Casperson, D., Ford, D., McKay, J.: An ideal decomposition Algorithm. J. Symbolic Comput. 21(2), 133–137 (1996)zbMATHCrossRefMathSciNetGoogle Scholar
  5. 5.
    von zur Gathen, J.: Functional decomposition of polynomials: the tame case. J. Symbolic Comput. 9(3), 281–299 (1990)zbMATHCrossRefMathSciNetGoogle Scholar
  6. 6.
    von zur Gathen, J.: Functional decomposition of polynomials: the wild case. J. Symbolic Comput. 10(5), 437–452 (1990)zbMATHCrossRefMathSciNetGoogle Scholar
  7. 7.
    Gutierrez, J.: A polynomial decomposition algorithm over factorial domains. C. R. Math. Rep. Acad. Sci. Canada 13(2-3), 81–86 (1991)zbMATHMathSciNetGoogle Scholar
  8. 8.
    Gutierrez, J., Recio, T., Ruiz de Velasco, C.: A polynomial decomposition algorithm of almost quadratic complexity. In: Mora, T. (ed.) AAECC 1988. LNCS, vol. 357, pp. 471–476. Springer, Heidelberg (1989)Google Scholar
  9. 9.
    Gutierrez, J., Rubio, R.: CADECOM: Computer Algebra software for functional DECOMposition. In: Ganzha, V.G., Mayr, E.W., Vorozhtsov, E.V. (eds.) Proceedings of the Second Workshop on Computer Algebra in Scientific Computing, Samarkand, Uzbekistan, pp. 233–248. Springer, Heidelberg (2000)Google Scholar
  10. 10.
    Gutierrez, J., Rubio, R., Sevilla, D.: On Multivariate Rational Function Decomposition. J. Symbolic Comput. 33(5), 545–562 (2002)zbMATHCrossRefMathSciNetGoogle Scholar
  11. 11.
    Gutierrez, J., Rubio, R., von zur Gathen, J.: Multivariate Polynomial decomposition. Applicable Algebra in Engineering, Communication and Computing 14(1), 11–31 (2003)zbMATHMathSciNetGoogle Scholar
  12. 12.
    Gutierrez, J., Sevilla, D.: On Ritt’s decomposition Theorem in the case of finite fields. Finite Fields and Their Applications 12(3), 403–412 (2006)zbMATHCrossRefMathSciNetGoogle Scholar
  13. 13.
    Kozen, D., Landau, S.: Polynomial decomposition algorithms. J. Symbolic Comput. 7(5), 445–456 (1989)zbMATHCrossRefMathSciNetGoogle Scholar
  14. 14.
    Nagata, M.: Theory of Commutative Fields. Translations of Mathematical Monographs, Amer. Math. Soc. 125 (1993)Google Scholar
  15. 15.
    Netto, E.: Ünber einen Lüroth-Gordaschen Satz. Math. Ann. 9, 310–318 (1895)CrossRefMathSciNetGoogle Scholar
  16. 16.
    Schinzel, A.: Selected Topics on Polynomials. University Michigan Press, Ann Arbor (1982)zbMATHGoogle Scholar
  17. 17.
    Schinzel, A.: Polynomials with special regard to reducibility. Cambridge University Press, New York (2000)zbMATHCrossRefGoogle Scholar
  18. 18.
    Zippel, R.: Rational Function Decomposition. In: Proc. ISSAC 1991, pp. 1–6. ACM Press, New York (1991)CrossRefGoogle Scholar

Copyright information

© Springer-Verlag Berlin Heidelberg 2006

Authors and Affiliations

  • Jaime Gutierrez
    • 1
  • David Sevilla
    • 2
  1. 1.Faculty of SciencesUniversity of CantabriaSantanderSpain
  2. 2.Dpt. of Computer Science and Software EngineeringConcordia UniversityMontréalCanada

Personalised recommendations