Let's say we will choose some 256-bit random $b$ and we will find the smallest $d$ such that:
$\frac {2^{d}-1}{b} = s$
Now compute $z \equiv s \pmod{2^{128}}$. If I will give you only $z$ - is it possible to compute $b$ in some acceptable time? Is it hard problem? Do we know some algorithm to compute it? Is it save enough to use $z$ as a public key and $b$ as a private key?
EDIT:
I made one mistake, $z$ should be compute in another way - just take $s$ and cut all bits except $128$ least significant. So $z$ is composed of $128$ least significant bits of $s$. It does not change much, probably.