0
$\begingroup$

I have learnt that there is a trick where you can speed up the reduction modulo of a point (x-value) in a x25519 curve. Since, it uses the prime number $2^{255} - 19$.

From article:

Reduction modulo exploits the fact that $2^{255} - 19$. $2^{256} \equiv 38$, so $38*r4$ is added $r0$ and $38*r5$ is added $r1$ and so on.

$r_n$ are registers with size 64 bits.

The problem I have. I don't really understand why this is the case? I wonder if anyone can expand on this?

$\endgroup$
1
1
$\begingroup$

Let $p = 2^{255} - 19$.

Clearly $p \equiv 0 \pmod p$, meaning $p$ (the modulus) divides $p - 0$ (the two sides of the equation), or equivalently: there exists some integer $k$ such that $p - 0 = k\cdot p$. (Here $k = 1$.)

So $2^{255} - 19 \equiv 0 \pmod p$, and thus $2^{255} \equiv 19 \pmod p$, meaning there exists some $k$ such that $2^{255} - 19 = k\cdot p$. (Here, again, $k = 1$.)

If we multiply both sides of the equation by $2$, then we get $2\cdot 2^{255} \equiv 2\cdot 19 \pmod p$, meaning there exists some integer $k$ such that $2\cdot 2^{255} - 2\cdot 19 = k\cdot p$. (Here $k = 2$.)

But this equation is just $2^{256} \equiv 38 \pmod p$.

Hence, whenever you are doing arithmetic modulo $p$, the quantities $2^{256}$ and $38$ are equivalent. Since reduction modulo $p$ is a ring homomorphism—that is, $$[(a + b) \bmod p] \equiv [(a \bmod p) + (b \bmod p)] \pmod p,$$ and likewise with multiplication—we can split a number $n$ into the low 256 bits $n_{\mathrm{lo}}$ and the rest $n_{\mathrm{hi}}$ so that $n = n_{\mathrm{lo}} + 2^{256} n_{\mathrm{hi}}$. Then $$n = n_{\mathrm{lo}} + 2^{256} n_{\mathrm{hi}} \equiv n_{\mathrm{lo}} + 38 n_{\mathrm{hi}} \pmod p.$$

$\endgroup$
1
  • $\begingroup$ Thanks for explanation! $\endgroup$ – einstein Nov 23 '19 at 10:28

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.