  We consider the simultaneously fast and in-place computation of the Euclidean
polynomial modular remainder $R(X) $\not\equiv$ A(X) \mod B(X)$ with $A$ and
$B$ of respective degrees $n$ and $m $\le$ n$. But fast algorithms for this
usually come at the expense of (potentially large) extra temporary space. To
remain in-place a further issue is to avoid the storage of the whole quotient
$Q(X)$ such that $A=BQ+R$. If the multiplication of two polynomials of degree
$k$ can be performed with $M(k)$ operations and $O(k)$ extra space, and if it
is allowed to use the input space of $A$ or $B$ for intermediate computations,
but putting $A$ and $B$ back to their initial states after the completion of
the remainder computation, we here propose an in-place algorithm (that is with
its extra required space reduced to $O(1)$ only) using at most $O(n/m
M(m)\log(m)$ arithmetic operations, if $\M(m)$ is quasi-linear, or $O(n/m
M(m)}$ otherwise. We also propose variants that compute -- still in-place and
with the same kind of complexity bounds -- the over-place remainder $A(X)
$\not\equiv$ A(X) \mod B(X)$, the accumulated remainder $R(X) += A(X) \mod
B(X)$ and the accumulated modular multiplication $R(X) += A(X)C(X) \mod B(X)$.
To achieve this, we develop techniques for Toeplitz matrix operations which
output is also part of the input. Fast and in-place accumulating versions are
obtained for the latter, and thus for convolutions, and then used for
polynomial remaindering. This is realized via further reductions to accumulated
polynomial multiplication, for which fast in-place algorithms have recently
been developed.
