Assume the complex to be a free resolution of :

The multiplication by induces a complex

Now, the tensor product (see Chapter 17.3 in [3]) of the two complexes is a double complex :

where the vertical mappings are the multiplications with for .

According to this lemma we construct the extension from 2 copies of the resolution and the homomorphism of complexes induced by . As arithmetical operations this procedure requires only duplication and addition of polynomials. The number of them depends on the size of . Thus, the involved operations are of polynomial complexity w.r.t. to the input of and .