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

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?

• that's because of the reduction after you note that $x^{18} = x^{10}\cdot x^8$. – ddddavidee May 11 '16 at 20:39
• I understand that $x^{10}$ is $2^{255}$ and that's why they are multiplied by $2^{-255}$, which would be a 255 bits right shift. What I don't understand is why it's also multiplied by 19. – Daniel Munoz May 11 '16 at 22:07
• I also understand that the 19 is in there because that 19 is present as a negative term of the module. But how does it ends multiplying $x^{18}$? – Daniel Munoz May 11 '16 at 22:24

$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.
• So, in the example you cited from the paper, if you have a polynomial with $a x^{18} + b x^8$ you can reduce as follows: $a x^{10}x^8 + b x^8 \equiv a \cdot x^{-255}\cdot 19\cdot x^8 + bx^8 \equiv (a \cdot x^{-255}\cdot 19 + b )x^8$. Similarly for the others couples (17, 7) and so on. – ddddavidee May 12 '16 at 7:12
• it should be read $2^{-255}$ on previous comment. Sorry. – ddddavidee May 12 '16 at 7:21