Factoring and decomposing ore polynomials over Fq(t)

ABSTRACT

We present algorithms for computing factorizations and least common left multiple (LCLM) decompositions of Ore polynomials over Fq(t), for a prime power q=p^μ. Our algorithms are effective in Fq(t)[D; σ,δ], for any automorphism σ and σ-derivation δ of Fq(t). On input f ∈ Fq(t)[D;σ,δ], the algorithms run in time polynomial in degD(f), degt(f), p and μ.

REFERENCES

• 1: S. A. Amitsur. Derivations in simple rings. Proc. London Mathematical Society, VII, 3rd series:87--112, 1957.
• 2: E. Beke. Die irreducibilität der homogenen linearen differentialgleichungen. Math. Annalen, 45:278--300, 1894.
• 3: J. Bergen and S. Montgomery. Smash products and outer derivations. Israel Journal of Mathematics, 53 (1):321--345, 1986.
• 4: M. Bronstein and M. Petkovšek. On Ore rings, linear operators and factorisation. Programmirovanie, 20:27--45, 1994.
• 5: Manuel Bronstein , Marko Petkovšek, An introduction to pseudo-linear algebra, Theoretical Computer Science, v.157 n.1, p.3-33, April 9, 1996
• 6: Thomas Cluzeau, Factorization of differential systems in characteristic p, Proceedings of the 2003 international symposium on Symbolic and algebraic computation, p.58-65, August 03-06, 2003, Philadelphia, PA, USA [doi>10.1145/860854.860875]
• 7: P. Cohn. Free Rings and their Relations. Academic Press, London, 1985.
• 8: P. Cohn. Skew Fields: Theory of General Division Rings. Cambridge, London, 1995.
• 9: M. Giesbrecht. Some results on the functional decomposition of polynomials. Master's thesis, University of Toronto, 1988. Also available as University of Toronto Technical Report 209/88.
• 10: Mark Giesbrecht, Factoring in Skew-Polynomial Rings, Proceedings of the 1st Latin American Symposium on Theoretical Informatics, p.191-203, April 06-10, 1992
• 11: Mark Giesbrecht, Factoring in skew-polynomial rings over finite fields, Journal of Symbolic Computation, v.26 n.4, p.463-486, Oct. 1998 [doi>10.1006/jsco.1998.0224]
• 12: Mark van Hoeij, Rational solutions of the mixed differential equation and its application to factorization of differential operators, Proceedings of the 1996 international symposium on Symbolic and algebraic computation, p.219-225, July 24-26, 1996, Zurich, Switzerland [doi>10.1145/236869.237078]
• 13: Mark Van Hoeij, Factorization of differential operators with rational functions coefficients, Journal of Symbolic Computation, v.24 n.5, p.537-561, Nov. 1997 [doi>10.1006/jsco.1997.0151]
• 14: Joris van der Hoeven, FFT-like multiplication of linear differential operators, Journal of Symbolic Computation, v.33 n.1, p.123-127, 01/01/2002 [doi>10.1006/jsco.2000.0496]
• 15: G. Ivanyos, L. Rónyai, and A. Szántó. Decomposition of algebras over $gfq(x1,...,xm). Applicable Algebra in Engineering, Communication and Computing, 5: 71--90, 1994.
• 16: N. Jacobson. The Theory of Rings. American Math. Soc., New York, 1943.
• 17: N. Jacobson. Finite-Dimensional Division Algebras over Fields. Springer-Verlag, 1996.
• 18: Ziming Li, A subresultant theory for Ore polynomials with applications, Proceedings of the 1998 international symposium on Symbolic and algebraic computation, p.132-139, August 13-15, 1998, Rostock, Germany [doi>10.1145/281508.281594]
• 19: Z. Li. Some bounds for skew polynomials, 2002. Preprint.
• 20: S. Montgomery. Fixed rings of finite automorphism groups of associative rings, volume 818 of Lecture Notes in Mathematics. Springer-Verlag, 1980.
• 21: O. Ore. Formale Theorie der linearen Differentialgleichungen. J. reine angew. Math., 168: 233--252, 1932.
• 22: O. Ore. On a special class of polynomials. Trans. Amer. Math. Soc., 35: 559--584, 1933a.
• 23: O. Ore. Theory of non-commutative polynomials. Annals of Mathematics, 34 (22): 480--508, 1933b.
• 24: O. Ore. Contributions to the theory of finite fields. Trans. Amer. Math. Soc., 36: 243--274, 1934.
• 25: M. van der Put. Differential equations in characteristic ρ. Compositio Mathematica, 97: 227--251, 1995.
• 26: M. van der Put. Reduction modulo ρ of differential equations. Indag. Mathem., 7 (3): 367--387, 1996.
• 27: M. van der Put. Modular methods for factoring differential operators. Unpublished manuscript, 34 pp., 1997.
• 28: M. van der Put and M.F. Singer. Galois Theory of Difference Equations. LNM 1666. Springer, 1997.
• 29: M. F. Singer. Testing reducibility of linear differential operators: A group theoretic perspective. Applicable Algebra in Engineering, Communication and Computing, 7 (2): 77--104, 1996.

INDEX TERMS

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

General Terms:
Algorithms

Keywords:
eigenring, factoring, modular, ore polynomial