Multiplying integers modulo $2^{255}-19$ using the Curve25519 polynomial reduction algorithm

Question

I'm reading the Curve25519 paper and I see that in page 11, under the title "Multiplying integers modulo $2^{255}-19$", it says:

The coefficients of $x^{10}$; $x^{11}$; ...; $x^{18}$ in $uv$ are eliminated by reduction modulo $2^{255}x^{10} - 19$. For example, the coefficient of $x^{18}$ is multiplied by $19 \cdot 2^{-255}$ and added to the coefficient of $x^8$.

I don't understand why that multiplication and similar others in coefficients 17/7, 16/6, 15/5, 14/4, 13/3, 12/2, 11/1, 10/0 reduce the polynomial modulo $2^{255}-19$ as the paper says.

What is the explanation for that? Does this algorithm has a name or something so I can read its description?

Answer 1

The paper states

$R$ contains $2^{255}x^{10}-19$, which represents $0$ in $\mathbb Z/(2^{255}-19)$.

In other (slightly simplified) words: $$x^{10} \;\;\text{is}\;\; 2^{-255}\cdot19 \text!$$ ^{(Note that this contradicts your comment to the question: $x^{10}$ does not represent $2^{255}$.)}

To understand this, recall that a value in $\mathbb Z/(2^{255}-19)$ is represented by a polynomial which has that value at the point $1$. Indeed, evaluating $2^{255}x^{10}-19$ at $1$ yields precisely the modulus $2^{255}-19$, hence identifying it with zero does not change the represented value. Now observe that reducing modulo $2^{255}x^{10}-19$ means identifying that polynomial with zero. The resulting relation can also be stated as $$\begin{align*} &2^{255}x^{10}-19 \;=\; 0 \\\iff\quad& 2^{255}x^{10} \;=\; 19 \\\iff\quad& x^{10} \;=\; 2^{-255}\cdot 19 \text, \end{align*}$$ as claimed. Thus you can always (for instance: when reducing degrees) replace $x^{10}$ by $2^{-255}\cdot19$ without changing the represented value.