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.)
Note that $q = 2^{252} + n$ for $n &lt; 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 &lt; 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}} &lt; 2^8$, so we can set the bound $$n^2 x_{\mathrm{hi}} &lt; 2^{250} 2^8 = 2^{253} &lt; 2^{253} n + n^2 = q^2 - 2^{504},$$ which puts the reduced sum $n^2 x_{\mathrm{hi}} + x_{\mathrm{lo}} &lt; q^2$ in the range of Barrett reduction.