Regarding wheather we assume 160 bit space or 159 (half of it).
The idea to "only" need to search in half of the 160-bit output space of addresses arises because we generate both,
compressed and uncompressed addresses for each private key guess.
Q: I don't know about that process. Is it more like this:
private_key --*some process*--> uncompressed-address
|
--*some other process*--> compressed-address
or like this:
private_key --*some process*--> uncompressed-address --*some other process*--> compressed-address
I would argue no search-space reduction can be achieved if the process is the later one.
So IMO the statement on the page "X bits of 160bits" is correct.
Regarding the probabilty calculations i guess arulbero is in a higher dimension than me Cheesy I'll shut up and enjoy the show Lips sealed
Leaving out some small details:
1) Securely generate a private key. This is basically a secure 256 bit random number. It is not exactly 256 bits because it has to be less than a certain specified 256 bit number but for the purposes here let's just consider it a 256 bit random number.
2) Calculate the public key. The formula is public_key = private_key * G. Where private_key is a very large random number, G is the specified starting point on the specified elliptic curve (the "Generator" point), * is the specified scalar multiplication operation over the group of points on the elliptic curve and private_key is the calculated point on the elliptic curve.
3) Note that public_key
is a point on an elliptic curve. It has an X and a Y coordinate to describe which point is is. But also note an interesting property of the X and the Y coordinates on all elliptic curves:
for every X coordinate on the curve there are only two possible Y coordinates. It is not exactly correct in our case here but you can think of them as the possible positive Y coordinate and the possible negative Y coordinate.
Now the uncompressed public_key is simply X and Y. So an uncompressed public key is 256 + 256 = 512 bits.
The compressed public key is X and a single bit, lets call it b, that tells you which of the two possible Y values to use. So a compressed public key is 256 + 1 = 257 bits. But you can easily calculate the full public key from the compressed public key by calculating the two possible Y coordinates from the X coordinate given and then using the single bit "b" to select which of the two Y coordinate values to use.
To get the
Bitcoin address from the public key you
either:
1) Take the full 512 bit public key (X, Y) and hash it down to 256 bits, then hash it down to 160 bits then encode the answer.
or2) Take the 257 bit compressed public key (X, b) and hash it down to 256 bits, then hash it down to 160 bits then encode the answer.
Both the uncompressed and compressed versions of the public key and the encoded hashed versions of the public key (the compressed and uncompressed versions of the Bitcoin address)
describe exactly the same point on the elliptic curve.
Therefore both the compressed and uncompressed versions of the Bitcoin address map back to exactly the same private key.
?
to find even one of them 
?