Meet in the Middle Attack on x=2^n + x' I encountered today the following equation:

$x = 2^n + x'$, where $0 \le x' &lt; 2^k &lt; 2^n$, $2|k$ and $n, k$ is known.

There seems to be a meet in the middle attack for this, with runtime $O(2^{\frac{k}{2}})$ but I don't see it. 

$x$ is known and we want to recover $x'$.

Could anyone give me a hint?

Thanks.
Well, if you absolutely had to do a MITM attack, I suppose one could look like:


Rewrite the equation as:


$$x  - x'_{low} = 2^h + 2^{k/2}x'_{high}$$

where $x' = 2^{k/2}x'_{high} + x'_{low}$ and $0 \le x'_{low}, x'_{high} &lt; 2^{k/2}$


For each $x'_{low}$ value in the range, compute $x - x'_{low}$ and place it in a list.
For each $x'_{high}$ value in the range, compute $2^h + 2^{k/2}x'_{high}$ and place it in a list.
Flip the order of the first list (normally, you're supposed to sort them; these are already in sorted order), and then scan through the two lists, and look for a value in common.


Yes, this is a silly way to do it; however it is a Man-in-the-Middle attack of the specified complexity; this might be the answer they're looking for...