Faster relaxed multiplication

In previous work, we have introduced several fast algorithms for relaxed power series multiplication (also known under the name on-line multiplication) up to a given order n. The fastest currently known algorithm works over an effective base field K with sufficiently many 2^p-th roots of unity and has algebraic time complexity O(n log ne² √ log 2 √ log log n). In this paper, we will generalize this algorithm to the cases when K is replaced by an effective ring of positive characteristic or by an effective ring of characteristic zero, which is also torsion-free as a ℤ-module and comes with an additional algorithm for partial division by integers. In particular, we may take K to be any effective field. We will also present an asymptotically faster algorithm for relaxed multiplication of p-adic numbers. Copyright is held by the owner/author(s).