Elliptic curve and "vanity" public keys I want to find an algorithm to get a private/public key pair where one coordinate of the public key has some specific prefix (for example: 20 leading zeroes).
In the secp256k1 case (the Bitcoin curve), G. Maxwell has found a public key with coordinate

x = 00000000000000000000003b78ce563f89a0ed9414f5aa28ad0d96d6795f9c63

( see https://bitcointalk.org/index.php?topic=90982.msg13789635#msg13789635).
In that case 22 zeroes means 88 bits, and he claimed to have found the private key too. Obviously $2^{88}$ random tries are computationally infeasible, then I think that the Birthday Paradox should be used (to reduce the steps from $2^{88}$ to $2^{44}$). But I can't understand how to apply the Pollard Rho algorithm (the classic Birthday Paradox - based algorithm) to this specific task.  Any ideas?
EDIT1:
It is very simple to find only a public key with as many leading zeros as you want without the private key, for example:

x = 0000000000000000000000000000000000000000000000000000000000000001
y = 4218f20ae6c646b363db68605822fb14264ca8d2587fdd6fbc750d587e76a7ee

are the coordinates of a valid point of the secp256k1 curve because they fulfill the equation $y^2 = x^3 + 7$ mod $p$
That's why I'm pretty sure that G.Maxwell has the private key too (otherwise his public key would have nothing special)
For now I know that if I generated about $2^{44}$ random points, I would find a &quot;partial&quot; collision, i.e. I would find a couple of points $P_1$, $P_2$ with $x_{P_1}$ and $x_{P_2}$ that share the first 88 bits. How do I use this information to find a point $P_3$ with 88 leading zero bits?
EDIT2:
Very strange: it seems that it takes $2^{88}$ steps to find a private key to any public key with a specific 88 bit prefix,
but it takes only $2^{128}$ steps to find a private key to a single specific public key (with a specific 256 bit &quot;prefix&quot;) using the Pollard Rho algorithm  (see http://andrea.corbellini.name/2015/06/08/elliptic-curve-cryptography-breaking-security-and-a-comparison-with-rsa/ or https://blog.coinfabrik.com/wp-content/uploads/2016/06/ECDSA-Security-in-Bitcoin-and-Ethereum-a-Research-Survey.pdf)
Then to find a private key to any public key with a specific m bit prefix, with $m&gt; n/2$, Pollard Rho is the best shot, with $m\leq n/2$ the fgrieu method is the best.
Maxwell's vanity public key is a result of how the generator of the secp256k1 was chosen; as explained by Maxwell himself.

For some reason, the generator $G$ is the double of the point:

x = 0x00000000000000000000003b78ce563f89a0ed9414f5aa28ad0d96d6795f9c63, 
y = 0xc0c686408d517dfd67c2367651380d00d126e4229631fd03f8ff35eef1a61e3c


which is exactly Maxwell's vanity public key. Its private key is 0x7fffffffffffffffffffffffffffffff5d576e7357a4501ddfe92f46681b20a1 which is $1/2$, i.e. the inverse of $2$ modulo the curve order $n$. This is also equal to $(n+1)/2$.

The big question is: why was the secp256k1 generator chosen like that? I have no idea. But note that it's not difficult to find a generator with a lot of leading zeroes.