5 ms·
Exactly. Any one can offer an explanation why they didn't take this path for 256-bit numbers instead?
by 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 agoTaking 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 agoTo 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 agoWhy would you ever worry about overflow of the leading chunk (aka limb)?
- dgoldstein0 6y agoBecause you want to know when your result is inaccurate?
- bonzini 6y agoBut you're operating modulo 2^256.
- kroeckx 6y agoBecause 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 agoAh, 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.