# 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?

## 1 Answer

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

• Is this a known algorithm, or ad-hoc? – MickLH Jan 25 '17 at 19:21
• @MickLH It has been well-known to practitioners for decades, e.g. Merrill 1964 (paywall-free). I wouldn't be surprised if a dedicated historian could trace it to Gauss or further. – Squeamish Ossifrage Mar 23 '19 at 9:05
• Can you provide a name for the algorithm? – Titanlord Jul 6 '20 at 14:44