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?

  • 2
    $\begingroup$ that's because of the reduction after you note that $x^{18} = x^{10}\cdot x^8$. $\endgroup$ – ddddavidee May 11 '16 at 20:39
  • $\begingroup$ 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. $\endgroup$ – Daniel Munoz May 11 '16 at 22:07
  • $\begingroup$ 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}$? $\endgroup$ – Daniel Munoz May 11 '16 at 22:24

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.

  • 1
    $\begingroup$ 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. $\endgroup$ – ddddavidee May 12 '16 at 7:12
  • $\begingroup$ it should be read $2^{-255}$ on previous comment. Sorry. $\endgroup$ – ddddavidee May 12 '16 at 7:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.