Recently I was reading some article about the Bernstein's Curve25519. This is a particular Montgomery curve over $\mathbb{F}_q$ where $q = {2^{255}-19}$.
What I missed or was unable to understand is what are the particular benefits of using a prime close to the power of 2. How does this for example help practically doing the reduction modulo $q$ of some number?
After a multiplication you have a number with $2 \cdot 255$ bits. Since $2^{255} = 19 \pmod q$, you can take the upper half, multiply it by 19 and add it to the lower half. This gives you an equivalent number smaller than $20 \cdot 2^{255}$. Repeat this to get a number that's smaller than $2 \cdot q$. Now check if the value is greater or equal to $q$ and subtract $q$.
Being close to a power-of-two matters in the first step. Since 19 is so small, the number after the first reduction step is only a few bits bigger than $q$.
If to the power-of-two the difference were bigger, the resulting number would be bigger and you'd need more steps to reduce it. If you have a random prime, the result is barely smaller than the input and you're better off with a different algorithm (such as montgomery reduction).
