Does a high exponent compensate for a low degree of certainty? If a RSA certificate is created with a low degree of certainty, does the value of the exponent compensate for this?

I'm asking because certain implementations of key generation software hide the certainty value from the administrator, and I'd like to find reassurance in any other parameter.

If the exponent doesn't compensate for this, does a longer key length compensate for certainty?
Well, no, having a longer exponent really doesn't compensate for low degree of certainty in the RSA key generation.

As you are well aware, the most common method for generating RSA keys involves finding primes by picking numbers, and using a probabilistic method to verify whether those numbers are prime.  These probabilistic methods have a small probability of claiming that a composite number is prime; the certainty factor that some implementations ask for is an indication of how small this error probability should be.

Now, if the certainty factor is too low, the error that might result is that one of the "primes" that are picked isn't really a prime.  This can cause two errors:


The RSA key might not work (or, at least, not consistently).  For example, if the RSA key is used for public key encryption, the private key might not correctly decrypt something encrypted with the public key.
The RSA key might work; this will happen if the 'prime' that got chosen happens to be a Carmichael number; that is, a composite number $n$ for which $x^n = x \mod n$ holds for all $x$.  Now, Carmichael numbers are rare (far rarer than primes), but they do exist.  The potential problem is that Carmichael number often have small factors; if someone notices that the RSA key has a small factor, they might be able to figure out the other factors of the Carmichael number, and thus factor the RSA key.


In both cases, using a larger public exponent won't help.  A larger RSA key also won't help much for case 1 (other than making it less likely that a nonprime will sneak through).  It might for case 2, but I wouldn't be real confident about it.

Now, if the key generation software doesn't allow you to specify a certainty factor, it means that either:


The software has a preset certainty factor build in; one would hope that it is set fairly conservatively (perhaps about as likely as hardware error), but you can certainly ask
The software doesn't use a probabilistic method.  There are deterministic methods of finding primes (such as the Shawe-Taylor algorithm, see A.1.2.1) that are approximately as efficient as probabilistic methods; perhaps those libraries do that.


On the other hand, if you don't trust some key generation software to do the right thing, perhaps you shouldn't use them.  There are some nasty things that a bugged RSA key generation software can do.