Hacker News Reader

Comment by gene91 | Hacker News Reader

Exactly. Any one can offer an explanation why they didn't take this path for 256-bit numbers instead?

Taking a guess: if you use this form to do a bunch of operations before normalizing, you don't need to worry as much about intermediate overflow. E.g. you could easily add 10 different 256 bit numbers in this form and normalize at the end. Whereas if the leading chunk is 64 bits, every addition can overflow.

So 52/51/51/51/51 seems like the more generally useful choice

To expand of that: the whole idea is that normalization is not applied after every step.

This approach is efficient when you know you have to add a bunch of numbers together. You add them up, and then normalize.

The example can be, e.g. doing long multiplication, or adding all numbers in a list.

(Just repeating what was said in the parent comment for emphasis)

Why would you ever worry about overflow of the leading chunk (aka limb)?

Because you want to know when your result is inaccurate?

But you're operating modulo 2^256.

Because in crypto, the math usually isn't mod 2^256. For instance in curve25519 you do do math mod 2^255-19, so they actually all fit in 51 bit.

Ah, then in that case it's actually five 51-bit limbs making up the required 255 bits. So probably the article has a slight mistake here assuming that 52 bits of the highest limb are used which led to an inaccurate reason when trying to explain why it's fine.

"Unfortunately, we can’t do that here – a 64-bit integer only has so many possible values" and "The remaining 12 or 13 bits give us the extra “digits” we need for preventing carries."

using 64 bit registers, but only using 51 bits, has no overflow. Using 64 bit adds in 64 bit registers overflows, making the carry updates more costly.

Reply on news.ycombinator.com