3 ms·
I’m confused by your comment, because it doesn’t seem like we’re disagreeing. The end result of Grover’s algorithm is that a 2^N keyspace can be searched in a w
by dsacco 9y ago
I’m confused by your comment, because it doesn’t seem like we’re disagreeing. The end result of Grover’s algorithm is that a 2^N keyspace can be searched in a worst case of 2^N/2 steps instead of 2^N steps. So yes, it does halve the number of items to be searched.
- joncampbelldev 9y ago2^10 = 1024 2^20 = 1048576
- deleted 9y ago[deleted]
- lou1306 9y agoO(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).
- jessriedel 9y agoMaybe you've just used "items" in a non-standard way? The number of bits (N) is indeed being halved, but the standard way of talking about Grover's search is that you're searching for an item in the "database" of bit configurations (i.e., keyspace), which is 2^N. No one would refer to the bits as "items".
- dsacco 9y agoAh, I see what you mean. Yes, I didn’t intend to refer to the bits themselves as items; rather I was referring to the bit-security.