In-place fast polynomial modular remainder
Jean‐Guillaume Dumas, Bruno Grenet · 2024
We consider the simultaneously fast and in-place computation of the Euclidean polynomial modular remainder Math 1 with A and B of respective degrees n and m ≤ n. Fast algorithms for this usually come at the expense of a linear amount of extra temporary space. In particular, they require to first compute and store the whole quotient Q(X) such that A = BQ + R.