3 ms·
O(2^(N/2)) is a quadratic speedup over O(2^N). Halving the search space, on the other hand, would only give you a linear speedup. Edit: just to be clear: one h
by lou1306 9y ago
O(2^(N/2)) is a quadratic speedup over O(2^N).
Halving the search space, on the other hand, would only give you a linear speedup.
Edit: just to be clear: one half of 2^N is just 2^(N-1).
- dsacco 9y agoYes, I see the issue now. I wasn’t referring to bits being halved. I was referring to bit-security (i.e. 128-bit versus 64-bit).