5 ms·

> Aside: Why 13 bits instead of 12? For our purposes, we’re going to ignore the carries in the most significant limb, allowing numbers to wrap when they overflo

> Aside: Why 13 bits instead of 12? For our purposes, we’re going to ignore the carries in the most significant limb, allowing numbers to wrap when they overflow past 2^256 - 1 (just like how unsigned addition works in C with normal size integer types). As a result, we can assign 52 bits to the most significant limb and ignore the fact that it will run out of room for carries before the other limbs do. If you're going to wrap, you could go all the way and assign 64 bits to the most significant limb; that way you save 12 bits which you can spread to the other four limbs. You can go from {52, 51, 51, 51, 51} to {64, 48, 48, 48, 48}, so you have a spare 16 bits instead of 13 bits.

gene91 6y ago
Exactly. Any one can offer an explanation why they didn't take this path for 256-bit numbers instead?
- deleted 6y ago
  [deleted]
- ChrisLomont 6y ago
  "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.
- dgoldstein0 6y ago
  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
  - romwell 6y ago
    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)
  - bonzini 6y ago
    Why would you ever worry about overflow of the leading chunk (aka limb)?
    - dgoldstein0 6y ago
      Because you want to know when your result is inaccurate?
      - bonzini 6y ago
        But you're operating modulo 2^256.
- kroeckx 6y ago
  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.
  - tspiteri 6y ago
    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.
beagle3 6y ago
Indeed, if you use only 48 bits, you could also parallelize using the FP hardware - the mantissa is 52 bits, so if you use 48 bit limbs, you have 16 rounds before carry. Which is much less than 16 (or even 13) bits, but for processors which have distinct FP vs. integer adders, and that can issue them in parallel - you might get a speed boost.

gene91 6y ago

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

deleted 6y ago
[deleted]
ChrisLomont 6y ago
"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.
dgoldstein0 6y ago
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
- romwell 6y ago
  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)
- bonzini 6y ago
  Why would you ever worry about overflow of the leading chunk (aka limb)?
  - dgoldstein0 6y ago
    Because you want to know when your result is inaccurate?
    - bonzini 6y ago
      But you're operating modulo 2^256.
kroeckx 6y ago
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.
- tspiteri 6y ago
  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.

beagle3 6y ago

Indeed, if you use only 48 bits, you could also parallelize using the FP hardware - the mantissa is 52 bits, so if you use 48 bit limbs, you have 16 rounds before carry. Which is much less than 16 (or even 13) bits, but for processors which have distinct FP vs. integer adders, and that can issue them in parallel - you might get a speed boost.