On short multiplications and divisions

Computing only the low degree terms of the product of two univariate polyno mials is called a short multiplication. By decomposition into subproblems, a short multiplication can be reduced to appropriate addition of the result s of a number of full multiplications. In this paper a new way of choosing the size of the subproblems is proposed. Computing the quotient of two poly nomials is called a short division. The ideas used in the short multiplicat ion algorithm are transferred to an algorithm for short divisions. Finally, several applications of short multiplications and divisions are pointed ou t.