COMPLEXITY OF FACTORING AND CALCULATING THE GCD OF LINEAR ORDINARY DIFFERENTIAL-OPERATORS

Let L=∑ 0≤k≤n ( fk/f) dk dkx be a linear differential operator with rational coefficients, where fk,f∈ℚ¯[X] and ℚ¯ is the field of algebraic numbers. Let deg⁡x(L)= max⁡ 0≤k≤n { deg⁡x ( fk), deg⁡x (f)} and let N be an upper bound on degx(Lj) for all possible factorizations of the form L = L1 L2 L3, where the operators Lj are of the same kind as L and L2, L3, are normalized to have leading coefficient 1. An algorithm is described that factors L within time (N ℒ)0(n where ℒ is the bit size of L. Moreover, a bound N ≤ exp((ℒ2n)2n) is obtained. We also exhibit a polynomial time algorithm for calculating the greatest common (right) divisor of a family of operators. © 1990, Academic Press Limited. All rights reserved.