Is modular Barrett reduction usable for Ed25519?
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.