Computing Characteristic Polynomials of p-Curvatures in Average Polynomial Time

Abstract

We design a fast algorithm that computes, for a given linear differential operator with coefficients in $Z[x]$, all the characteristic polynomials of its p-curvatures, for all primes $p<N$ , in asymptotically 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.