We present an algorithm to compute LCLM-decompositions for linear differentials operators with coefficients in the rational function field of characteristic p, \(\mathbb {F}_{p^n}(t)\). We show that for an operator L of order r with coefficients of degree d, it finishes in polynomial time in r, d and p. This algorithm proceeds in three steps. We begin by showing that the “type” of the factorisation of L can be easily obtained from the Frobenius normal form of its p-curvature, which can be efficiently computed using [4]. Using results from the thesis of the author [19], we are then able to construct an operator L* in the same equivalence class as L for which an LCLM-decomposition is known. Finally, by computing an isomorphism between the quotient modules \(\mathbb {F}_q(t)\langle \partial \rangle /\mathbb {F}_q(t)\langle \partial \rangle L^*\) and \(\mathbb {F}_q(t)\langle \partial \rangle /\mathbb {F}_q(t)\langle \partial \rangle L\), we find a corresponding LCLM-decomposition of L.

We design a fast algorithm that computes, for a given linear differential operator with coefficients in 918;[x], all the characteristic polynomials of its p-curvatures, for all primes p < N, in asymptoti- cally quasi-linear bit complexity in N. We discuss implementations and applications of our algorithm. We shall see in particular that the good performances of our algorithm are quickly visible.