# What are the computational benefits of primes close to the power of 2?

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