2 ms·
> you can solve your underdetermined system of 32 equations with 36 unknowns using your favorite technique What's the time complexity of your favorite techniqu
by Retr0id 4y ago
> you can solve your underdetermined system of 32 equations with 36 unknowns using your favorite technique
What's the time complexity of your favorite technique?
(I'm a bit out-of-the-loop on the specifics of equation solving techniques - I let Z3 do this kind of thing for me, and take an educated guess on whether I'll finish during my lifetime or not)
- orlp 4y agoJust naive Gaussian Elimination works in any field.
- Retr0id 4y agoWith what time complexity?
- orlp 4y agoO(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.