Again, we must wait to see the final parameters and optimized implementations. It seems likely they'll pick
n=144 and k=5, which means they need to find collisions on 16 bits at a time. That is just a lookup in a 64K entry table;
I don't expect to see any real sorting there. It's less clear how the actual items are represented, and if they are moved
themselves, or by pointer.
I believe you have the constants wrong. n=144, k=5 means that they're finding collisions
on n/(k+1) = n/6 = 24 bits at a time, repeated 4 times, and then finding final collisions
on the remaining 144-(4*24) = 48 bits, each time from a set of approximately 2^25
candidate hashes.
You're right; I somehow managed to mess up a trivial calculation. Thanks for the correction.
It's quite intriguing algorithmically. I think the original paper might be a little too glib about the constants, though.
Which constants are you referring to?
Btw, nice to see you back after a 10 month hiatus...