von zur Gathen, Joachim Functional decomposition of polynomials: the wild case. (English) Zbl 0722.12003 J. Symb. Comput. 10, No. 5, 437-452 (1990). Let \(F\) be a field, \(g,h\in F[x]\) and \(f=g\circ h=g(h)\in F[x]\). Then \((g,h)\) is said to be a decomposition of \(f\). For every \(f\) there exists an essentially unique complete decomposition in indecomposable polynomials, given that the characteristic \(p\) of \(F\) does not divide the degree of \(f\). The authors consider the following decomposition problem: given \(f\) of degree \(n\) and \(r,s\in \mathbb{N}\) with \(n=rs\), decide whether there exist \(g,h\in F[x]\) of degrees \(r,s\) respectively, such that \(f=g\circ h\). There exists an exponential-time algorithm if \(\text{char}(F)=0\) and in general for the “tame” case (\(p\) does not divide \(r\)) [the author [J. Symb. Comput. 9, No. 3, 281-299 (1990; Zbl 0716.68053)]. For the “wild” case, there is an algorithm over fields with a factorization procedure for univariate polynomials, given by D. Kozen and S. Landau [J. Symb. Comput. 7, No. 5, 445–456 (1989; Zbl 0691.68030)], polynomial-time for \(f\) irreducible and \(F\) finite; a complete decomposition is found in time \(O(n^{\log n})\) for \(F\) arbitrary with a polynomial-time factorization and \(f\) irreducible. Uniqueness is provided by Ritt’s First Theorem. The present paper extends Kozen and Landau’s work of directly solving the equations obtained from comparing coefficients in \(f=g\circ h\) to the wild case, where \(p\leq r<n\). An algorithm is obtained for the special case: Let \(\deg g=r=qt\) with \(q\) a power of \(p\), \(p\) does not divide \(t\), and \(q\geq p\). \(g\) is called simple if \(g=x^ r+b_{r-i}x^{r-i}+b_{r-i- 1}x^{r-i-1}+\ldots+b_ 0\), where \(b_{r-i}\neq 0\) and either \(p\) does not divide \(i\) or \(i\geq q\). The author provides a polynomial-time reduction from simple decompositions \(f=g\circ h\) with \(g\) simple to factorization of polynomials with degree less than \(n\). This gives a deterministic polynomial-time algorithm over finite fields. This can be viewed as exhibiting a further significant case of polynomial decomposition which is reasonably easy to solve; the general case still awaits a polynomial-time solution. Reviewer: Geert Molenberghs (Antwerpen) Cited in 19 Documents MSC: 12E05 Polynomials in general fields (irreducibility, etc.) 12Y05 Computational aspects of field theory and polynomials (MSC2010) 11Y16 Number-theoretic algorithms; complexity 68W10 Parallel algorithms in computer science 68W30 Symbolic computation and algebraic computation 11T06 Polynomials over finite fields Keywords:functional decomposition; exponential-time; wild case; tame case; complete decomposition; polynomial-time algorithm Citations:Zbl 0716.68053; Zbl 0691.68030 PDFBibTeX XMLCite \textit{J. von zur Gathen}, J. Symb. Comput. 10, No. 5, 437--452 (1990; Zbl 0722.12003) Full Text: DOI References: [1] Alagar, V. S.; Thanh, M., Fast polynomial decomposition algorithms, (Proc. EUROCAL 85. Proc. EUROCAL 85, Lecture Notes in Computer Science, 204 (1985), Heidelberg: Heidelberg Springer Verlag), 150-153 [2] Barton, D. R.; Zippel, R., Polynomial decomposition algorithms, J. Symb. Comp., 1, 159-168 (1985) · Zbl 0605.12012 [3] Cantor, D. G.; Kaltofen, E., Fast multiplication of polynomials over arbitrary rings, (Tech. Rep. 87-35 (1987), Dept. of Computer Science, Rensselaer Polytechnic Institute), 16, Acta Inf., to appear [4] Chistov, A. L.; Grigoryev, D. Yu., Polynomial-time factoring of the multivariable polynomials over a global field, LOMI preprint E-5-82 (1982), Leningrad · Zbl 0509.68029 [5] Dickerson, M., The Inverse of an Automorphism in Polynomial Time, (Proc. 30th Ann. IEEE Symp (1989), Foundations of Computer Science, Research Triangle Park NC), 82-87 [6] Dorey, F.; Whaples, G., Prime and composite polynomials, J. Algebra, 28, 88-101 (1974) · Zbl 0286.12102 [7] Fried, M. D.; MacRae, R. E., On curves with separated variables, Math. Ann., 180, 220-226 (1969) · Zbl 0185.28803 [8] Fröhlich, A.; Shepherdson, J. C., Effective Procedures in Field Theory, Phil. Trans., Royal Soc. Ser. A, 248, 407-432 (1955-56) · Zbl 0070.03502 [9] von zur Gathen, J., Hensel and Newton methods in valuation rings, Math. Comp., 42, 637-661 (1984) · Zbl 0581.13001 [10] von zur Gathen, J., Parallel algorithms for, algebraic problems, SIAM J. Comput., 13, 802-824 (1984) · Zbl 0553.68032 [11] von zur Gathen, J., Functional decomposition of polynomials: the tame case, J. Symb. Comp., 9, 281-299 (1990) · Zbl 0716.68053 [12] von zur Gathen, J.; Landau, S.; Kozen, D., Functional decomposition of polynomials, (Proc. 28th Ann. IEEE Symp (1987), Foundations of Computer Science: Foundations of Computer Science Los Angeles CA), 127-131 [13] Giesbrecht, M., Some results on the functional decomposition of polynomials, Tech. Rep. 209/88 (1988), Dept. of Computer Science, University of Toronto [14] Gutiérrez, J.; Recio, T.; Ruíz de Velasco, C., Polynomial decomposition algorithm of almost quadratic complexity, Springer Lecture Notes in Comp. Sci., 357, 471-476 (1989) · Zbl 0673.13002 [15] Hasse, H., Number Theory, (Grundlehren der math. Wiss (1980), Springer Verlag), 229 [16] Kozen, D.; Landau, S., Polynomial decomposition algorithms, J. Symb. Comp., 7, 445-456 (1989) · Zbl 0691.68030 [17] Ritt, J. F., Prime and composite polynomials, Trans. Amer. Math. Soc., 23, 51-66 (1922) · JFM 48.0079.01 [18] Schönhage, A., Schnelle Multiplikation von Polynomen über Körpern der Charakteristik 2, Acts, Informatica, 7, 395-398 (1977) · Zbl 0362.65011 [19] Schönhage, A.; Strassen, V., Schnelle Multiplikation grosser Zahlen, Computing, 7, 281-292 (1971) · Zbl 0223.68007 This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.