6
$\begingroup$

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?

$\endgroup$
7
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ Is this a known algorithm, or ad-hoc? $\endgroup$ – MickLH Jan 25 '17 at 19:21
  • $\begingroup$ @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. $\endgroup$ – Squeamish Ossifrage Mar 23 at 9:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.