An option strictly matching the question's statement (which requires $e=65537$) is to choose the public modulus $n$ as the product of many small primes $p_i$, perhaps $k=64$ primes of $32$ bits. That's multiprime RSA pushed to the max. The potential speedup is considerable. For small $k$, and standard arithmetic (quadratic multiplication and modular reduction) the speedup compared to normal RSA with CRT is in the order of $k^2/4$; that won't quite scale up to $k=64$, but we can get a speedup by a factor like $300$ or more (justified below).
We can also restricting to primes $p_i$ such that $d_i=e^{-1}\bmod(p_i-1)$ makes raising to the power $d_i$ less costly than for random choice of $p_i$ (if we use the basic exponentiation method: minimizing the sum of the number of bits in $d_i$ plus its Hamming weight). For a simple example, we restrict to the highest 32-bit primes $p_i$ of the form $p=(65537(4m+1)+1)/2$, get $p_0=4294148083, \dots, p_{63}=4203051653$, and $n$ is the (barely) 2048-bit 0x83658dd3af65c3aa48d7741adc0b9043f22501ef022d4b6c4e4ce93aea15b3410f94b1fd57ded3aa2abdcf90c4d05e564158261a28ce620655dc3d6cf2bbfb2ad57a3e9fd1b3c1c6c93e36f1f8fca29c8f0ba1f52458d7912f70d96e4ca447f0adc1de6e8692fc83201987fc7879f28fe8cc3a135ee38f31c240055d0c250ac55301b6229f698ab3d2fc909f28caff4f6f55bb674a003c83daac7964a285ce6d5485e5137e74c202cec0ff0a64b8c1d613ba70af875a6a49c6e36b13b57b4821a74bc65d03bcf5632e979996d5ad61f4844d1217413b4ab5aa804b1d8d04764fab01ade454b358db4710ba0ec82ae385423f9cf51ea11a6bdd1f1fcba1b1383b; each of the $d_i=(2p_i-1)/65537$ is 17-bit (a significant gain compared to about 31-bit with arbitrary choice of $p_i$). The execution time for a simple implementation computing $x^d\bmod n$ for $n$ of $b=2048$-bit is dominated by three steps:
- modular reductions of $x$ modulo each of the prime $p_i$, for a total $64\cdot63=4032$ modular reductions of 64-bit modulo a 32-bit $p_i$;
- 64 modular exponentiations, for a total of $1693$ (if I counted right) 32-bit multiplications giving 64-bit result followed by modular reduction to 32-bit;
- reconstruction of the result using the CRT, which should require (using a binary tree with width of results doubling each time we move closer to the root) about twice as many elementary operations as in regular RSA with CRT, where it can be done with about $3200$ 32-bit multiplications and accumulation of the 64-bit result.
Compare to about 6 million 32-bit multiplications and accumulation of the 64-bit result (for the equivalent of step 2) in regular RSA with CRT.
[If we can amortize computations over significant use, we can further optimize step 2, thus gain a little, by choosing even smaller $p_i$ (thus even more of them), and precomputing $x^{e^{-1}\bmod(p_i-1)}$ for every $x\in\{0,\dots,p_i-1\}$. For $k=128$, 20 MB of RAM are enough. Other costs are only marginally raised.]
As long as the certification authority is not more zealous than stated in standard Certificate Practice Statements (by trying to factor your $n$ even so slightly), it should deliver a certificate for such key; and things will be perfectly compatible with anything around not manipulating the private key and not trying to factor $n$. But there is a high risk to be exposed as using such trick. In fact any trick giving you a sizable speedup that I can imagine will expose you to that risk.
The above gives no security: anyone caring can factor $n$ (then act as the key owner, including in many cases revoking the key). Factoring is not even necessary in Poncho's system. However that comment suggests that keeping some level of security suitable for short term use might be what the question is about. In the following, I consider how far we can raise $k$ without becoming ridiculously weak.
When we use $k$ primes of about equal size, they will be about $2048/k$ bits. The best known factoring algorithm able to take advantage of small factors in $n$ is ECM. The largest factor ever found by ECM is 273-bit, and only two are above 256-bit. It is thus reasonable to believe that $k=8$ still leaves some security, while it does give a speedup of about $15$ compared to standard RSA with CRT.
