We introduce a variety of noncommutative polynomials that represent divide-and-conquer recurrence systems. Our setting involves at the same time variables that behave like words in purely noncommutative algebras and variables governed by commutation rules like in skew polynomial rings. We then develop a Gröbner-basis theory for left ideals of such polynomials. Strikingly, the nature of commutations generally prevents the leading monomial of a polynomial product to be the product of the leading monomials. To overcome the difficulty, we consider a specific monomial ordering, together with a restriction to monic divisors in intermediate steps. After obtaining an analogue of Buchberger's algorithm, we develop a variant of the F4 algorithm, whose speed we compare.

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~Nth coefficient of an algebraic series uses differential equations and has arithmetic complexity quasi-linear in √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.