Composing power series over a finite ring in essentially linear time (Q1267071)

Given power series \(u, v\) with first \(n\) terms and with \(v(0)=0\), over a finite commutative ring \(R\), the paper gives an algorithm for computation of the first \(n\) terms of \(u(v)\), when \(R\) has a non-zero characteristic. This is done in \(n^{1+o(1)}\) ring operations; this is fast, when \(R\) has a small characteristic. The procedure is discussed for prime and prime power characteristic, then the chinese remainder theorem is invoked for other cases (Knuth).