Fast Computation of the $N$th Term of an Algebraic Series over a Finite Prime Field
Résumé
We address the question of computing one selected term of an
algebraic power series. In characteristic zero, the best algorithm currently
known for computing the~$N$th coefficient of an algebraic series uses
differential equations and has arithmetic complexity quasi-linear
in~$\sqrt{N}$. We show that over a prime field of positive characteristic~$p$,
the complexity can be lowered to~$O(\log N)$. The mathematical basis for this
dramatic improvement is a classical theorem stating that a formal power series
with coefficients in a finite field is algebraic if and only if the sequence
of its coefficients can be generated by an automaton. We revisit and enhance
two constructive proofs of this result for finite prime fields. The first
proof uses Mahler equations, whose sizes appear to be prohibitively large. The
second proof relies on diagonals of rational functions; we turn it into an
efficient algorithm, of complexity linear in~$\log N$ and quasi-linear in~$p$.