Also dont forget:
The Problem we have is, that we don't know if the last bit is even or odd. If you know if the last bit is even or odd, you can crack any public key in no time.
How does this affect? Please explain in more detail..
You can always shift down a public key, aka halving a public key. You get two new public keys. But one is really halving and the other one is moving to the key middle range.
E.g.
You have the public key of 4 (binary represantation is 100). You halve it, and get the public key of 2 (10) and the public key of midrange - 2.
You have the public key of 5 (binary representation is 101). You halve it, and get the public key of public key of midrange - 2 or 3 and 2 (binary 10).
As you dont know the lowest bit, you can not determine which one of the pubkeys is the one you need. So you you have to take both and check them for the correct result.