Remix.run Logo
adrian_b 2 days ago

Which bits are the best is completely dependent on the particular hash function.

For instance, if the last operation during computing a hash function was the kind of integer multiplication where the result has the same length as the operands, then the top bits are the best (because they depend on more of the input bits than the bottom result bits).

On the other hand, if the last operation during computing a hash function was the kind of integer multiplication where the result has a length that is the sum of the lengths of the operands (i.e. where the high bits of the result are not discarded), then the best bits of the result are neither the top bits nor the bottom bits, but the middle bits, for the same reason as before, they are the bits that depend on more of the input bits than either the bottom bits or the top bits of the result. (This fact becomes obvious if you do a long multiplication with pen on paper. After you compute the partial products and you start to add them, you can see that when computing either the top digits or the bottom digits you need to add much less digits from the partial products than when you compute the middle digits, so the middle digits are more thoroughly mixed as functions of the input digits.)

When the last operation is an addition, because the carry bits propagate from the bottom bits towards the top bits, the top bits are the best, because the higher a bit is in the result there are more input bits on which it depends.