3 ms·
O(n^2 * w) where n is the number of equations and w is the number of elements in an equation.
by orlp 4y ago
O(n^2 * w) where n is the number of equations and w is the number of elements in an equation.
- Retr0id 4y agoI see. So in this instance, it's O(32^2 * 36)? That is better than 2^19, depending on implementation efficiency.
- orlp 4y agoWell to make the playing field equal it would be 2^19 times the time to check a solution, which is another factor of 36 times a fairly large constant C. So really you're comparing 2^19*C to 32^2.
- amluto 4y agoYou’re missing the constant factors. Gaussian elimination on a matrix containing 32-bit elements using xor involves operations that likely take a single cycle. The brute-force and meet-in-the-middle operations involve CRC-ing an entire message, which is vastly slower. (Or it involves optimizing the CRC using essentially the same linear algebra technique, at which would it would be pretty silly to solve a linear system by exhaustive search instead of algebra…) I would expect the linear algebra approach to win by orders or magnitude.
- Retr0id 4y agoI did my meet-in-the-middle using a search tree, so you don't need to re-CRC the whole message at once.