5 ms·
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],
by yorwba 5y ago
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.)
- moyix 5y agoNice 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 https://github.com/Sc00bz/copilot-hash-collider
- TimonKnigge 5y agoSurely 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.
- moyix 5y agoYes, 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.