# Is modular Barrett reduction usable for Ed25519?

I currently try to implement Ed25519 following this draft. I have implemented every field operation except the reduction by the group order $q$ (in chapter 5). I looked for a reduction algorithm and found montgomery reduction and barrett reduction. Because Barrett reduction seems to be more fitting I tried to understand how to implement it (mainly using this).

What I don't understand is how I can reduce a SHA512 hash by $q$, as the maximum possible value to reduce is ca. $2^{504}$ ($q$ is $2^{252}$, meaning $q^{2} = 2^{504}$). Is there a trick to reduce it in a step before that (like in curve25519 with $2^{256-38}$) or is Barrett reduction simply not usable here? (I don't necessarily need the fastest method available, a simple working one would be enough.)

• The order is still pretty close to a power-of-two, so you can use a variant of the approach described at: What are the computational benefits of primes close to the power of 2? – CodesInChaos Aug 2 '15 at 10:25
• A simple (but inefficient) method to reduce X, goes somehow as follows: You initialize $t=q<<256$. Then, you make a loop with 257 repetitions and in each step you subtract $t$ from $X$ if you have $X>t$, and you set $t=t>>1$. – Chris Aug 3 '15 at 14:30

Note that $$q = 2^{252} + n$$ for $$n < 2^{125}$$. Consequently, $$2^{252} \equiv -n \pmod q$$, so $$2^{504} \equiv (2^{252})^2 \equiv (-n)^2 \equiv n^2 \pmod q.$$ Since $$n^2 < 2^{250}$$, you can reduce $$2^{504} x_{\mathrm{hi}} + x_{\mathrm{lo}} \equiv n^2 x_{\mathrm{hi}} + x_{\mathrm{lo}} \pmod q.$$ Since the original input was only 512 bits long, $$x_{\mathrm{hi}} < 2^8$$, so we can set the bound $$n^2 x_{\mathrm{hi}} < 2^{250} 2^8 = 2^{253} < 2^{253} n + n^2 = q^2 - 2^{504},$$ which puts the reduced sum $$n^2 x_{\mathrm{hi}} + x_{\mathrm{lo}} < q^2$$ in the range of Barrett reduction.