4 ms·
> flip through all possible states of those n bits How do you do that in one pass?
by selcuka 4y ago
> flip through all possible states of those n bits
How do you do that in one pass?
- dataflow 4y agoBy not reading the input again and just keeping the n-bit counter in unrelated memory, since the actual input is kind of irrelevant for this, only its size. Again, may or may not apply depending on what precisely they meant by a "fixed" additional amount of memory...
- fdupress 4y agoHash the input (O(n)), search for a second preimage (very much not O(n) if you use a cryptographic hash).