RSA least significant bit oracle attack
Here's the next step in the iteration, which should be easy to understand:
Let's call the oracle on 2P and 4P:

Answer (even,even) means, that $P&lt;N/4$ (this is still easy: Otherwise either 2P or 4P would be greater than N).
(even,odd) means $N/4\le P&lt;N/2$.
(odd,even) means $N/2\le P&lt;3N/4$
(odd,odd) means $3/4N\le P&lt;N$.

If you continue with multiplying the factor for P with 2, you get the next round of iteration, where &quot;odd&quot; indicates the upper half of the interval and &quot;even&quot; indicates the lower half.