How much can we compress RSA public keys? I am wondering to what degree we can define an RSA variant, with a security argument that it is as safe as regular RSA with a given modulus size $m$ (e.g. $m=2048$), in which the public key has a compact representation of $k \ll m$ bits.

We can fix the public exponent to our favorite customary value, e.g. $e=2^{16}+1$ or $e=3$, thus need to store only the public modulus $n$. We need not store the leftmost bit of $n$, which is always set by definition; nor the rightmost bit, which is always set since $n$ is odd. With a little effort, we could save (very) few more bits noticing $n$ has no small divisors, but that will still be $k \sim m$ bits.

We can do better by forcing the $\left\lfloor m/2-\log_2(m)-2\right\rfloor$ high bits of $n$ to some arbitrary constant such as $\left\lfloor\pi \cdot 2^{\left\lfloor m/2-log_2(m)-4\right\rfloor}\right\rfloor$.
Observe that we can chose the smallest prime factor $p$ of $n$ just as we would do in regular RSA, then find the maximum integer interval $[q_0,q_1]$ such that any $q$ in that interval cause $n=p\cdot q$ to have the right high bits, then pick a random prime $q$ in that interval (most often there will be at least one, if not we try another $p$).
Some of the security argument is that


generating an RSA key $(p,q')$ using a regular method, with random huge primes in some appropriate range and no other criteria beside the number of bits in $n'=p\cdot q'$, and $p&lt;q$;
then deciding the high bits of $n$ from those in $n'$;
then finding $[q_0,q_1]$, generating $q$ as a random prime in that interval, and setting $n=p\cdot q$;


demonstrably gives the same distribution of $(p,q)$ as said regular generation method, hence is as secure; then we remark that the high bits of $n$ are random (with some distribution not too far from uniform), and public, thus fixing it can't much help an attack (I think this can be made rigorous).

This is now $k \sim m/2+\log_2(m)$ bits to express the public key. We can save a few more bits, each one at worse doubles the amount of work to generate the private key (we can repeat the generation process outlined above until we find a key with these bits equal to some public arbitrary constant; or equal to bits from a hash of the other bits if we want a tighter assurance that the scheme is not weakened).

Can we do better, and what's the practical limit?

Update: In RSA Moduli with a Predetermined Portion: Techniques and Applications, Marc Joye discuses this, and reaches $k \sim m/3$ (without claim of optimality). I'm worried that I do not see an argument that the manner in which $(p,q)$ are selected in Algorithm 3 does not weaken $n$ against a dedicated factoring algorithm.
Daniel J. Bernstein mentioned your way of compressing RSA public keys in his paper "A secure public-key signature system with extremely fast verification".
The naive way you outline roughly doubles the work for each extra bit. If there were a better method which did not run very slowly then it could be repurposed as a factoring algorithm.
So if it were possible to decompress arbitrary 104 to 128-bit strings into secure 2048-bit RSA public keys faster than factoring as David Schwartz suggests then that would be quite remarkable. Every time you ran the algorithm you'd effectively be finding the approximately equal sized factors of some 2048bit number of which you'd specified a lot of the bits.
Although there's no theoretical reason I can think of why this should be impossible, nor would it render RSA necessarily insecure, it does strike me as rather unlikely.

As you hint, a further (impractical) way to reduce the storage of the unspecified low bits of the modulus would be to store their residues modulo various small primes and reconstruct using the CRT. In theory this should save between 3 to 4 bits for a 2048-bit modulus. You save the space because you can rely on the residues not being zero.