Hacker News Reader

The meet-in-the middle algorithm seems like it could be further optimized. It solves for (((i << 32) + result32) ^ ch) % 33 == 0 by checking each i in [0..32], but since the xor doesn't affect any of the bits of i, it only needs to be applied to result32, which means that the equation is equivalent to (i << 32) % 33 == (33 - (result32 ^ ch)) % 33, which can be solved with a lookup table. (Basically an inverse of the MOD table already used in the code.)

View on HN

Nice trick! Unfortunately at this point the bottleneck really is not on generating candidates but on evaluating them. The existing early-exit code from Sc00bz [1] can generate all the lowercase alpha possibilities up to 13 letters in about half an hour, but it's not feasible to run all ~500 million of those through GPT2. Hoping to have some time to train a much dumber but much faster HMM to do the job.

[1] https://github.com/Sc00bz/copilot-hash-collider

Surely you can do some basic filtering by checking if the ratio vowels :: consonants is not too large? Or if there are five consonants in a row or something.

Yes, but even if that eliminates 99% of the candidates that's still 5 million 13-letter words to read through. And it would have excluded qrsqrt.

Reply on news.ycombinator.com