RSA public keys most commonly use 65537 (0x10001) as the public exponent. The sliding window exponentation algorithm the BigInteger class uses is ineffective in this case, you only pay the precomputation penalty. It should be disabled for this exponent.

I measure a 6-8% performance improvement for RSA public key operations using this exponent on SPARC/x86 with both C1 and C2, see suggested fix. RSA like benchmark program attached.