On the number of multiplications needed to invert a monic power series over fields of characteristic two
Let P (X) = 1 + a(1)X + a(2)X(2) + be a monic power series in X with indeterminates a(1), a(2).... as coefficients. The coefficients b(1), b(2),... of the inverse of P are polynomials in the coefficients of P. We prove that if divisions are forbidden, then at least n + 2[n/3] - 3 essential multiplications are needed to compute b(1),..., b(n), from a(1),..., a(n) over fields of characteristic two. (c) 2005 Elsevier Inc. All rights reserved.
inversion of power series multiplicative complexity