Explaining modulo reduction of curve25519, multiply hi bits with 38 trick?

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$$.

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?

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.$$

• Thanks for explanation! – einstein Nov 23 '19 at 10:28