This RFC says the RSA Exponent should be 65537.  Why is that number recommended and what are the theoretical and practical impacts & risks of making that number higher or lower? 

What are the impacts of making that value a non-Fermat number, or simply non prime?

Using $e\ne65537$ would reduce compatibility with existing hardware or software, and break conformance to some standards or prescriptions of security authorities. Any higher $e$ would make the public RSA operation (used for encryption, or signature verification) slower. Some lower $e$, in particular $e=3$, would make that operation appreciably faster (up to 8.5 times). If using a proper padding scheme, the choice of $e$ is not known to make a security difference; but for many less than perfect padding schemes that have been (or are still) used, high values of $e$ (compared to the number of bits in the public modulus $n$) are generally safer.



$e=65537$ is a common compromise between being high, and increasing the cost of raising to the $e$-th power: any higher odd $e$ cost at least one more multiplication (or squaring), which is true for odd exponents of the form $2^k+1$. Also, $e=65537$ is prime, which slightly simplify generating a prime $p$ suitable as RSA modulus, implying $\gcd(p-1,e)=1$, which reduce to $p\not\equiv 1\pmod e$ for prime $e$. Only the Fermat primes $3,5,17,257,65537$ have both properties, and all are common choices of $e$. It is conjectured that there are no other Fermat prime; and if there was any, it would we unusably huge.

Using $e=65537$ (or higher) in RSA is an extra precaution against a variety of attacks that are possible when bad message padding is used; these attacks tend to be more likely or devastating with much smaller $e$. Using $e=3$ would otherwise be attractive, since raising to the power $e=3$ cost 1 squaring and 1 multiplication, to be compared to 16 squaring and 1 multiplication when raising to the power $e=65537=2^{16}+1$.

For example, RSA with $e=65537$ has a security advantage over $e=3$ when:


Sending a message naively encrypted as $\mathtt{ciphertext}=\mathtt{plaintext}^e\bmod n$; the greater $e$ makes it more likely that $\log_2(\mathtt{plaintext})\gg \log_2(n)/e$ (which is necessary for security).
Sending the same message encrypted to $k$ recipients using the same padding (including any deterministic padding independent of $n$); the greater $e$ makes it less likely that $k\ge e$  (which allows a break).
Signing messages chosen by the adversary with a bad signature scheme. For example, with the scheme of the (withdrawn) ISO/IEC 9796 standard (described in HAC section 11.3.5), the adversary could obtain a forged signature from only 1 legitimate signature if $e=3$, but needs 3 legitimate signatures for $e=65537$; trust me on that one. The security advantage of $e=65537$ is wider for attacks against scheme 1 of the (current) ISO/IEC 9796-2.


For more explanations and examples of the risk of the combination of questionable message padding and low $e$, see section 4 in Dan Boneh's Twenty Years of Attacks on the RSA Cryptosystem.



There is no known technical imperative not to use $e=3$ when using a sound message padding scheme, such as RSAES-OAEP or RSASSA-PSS from PKCS#1, or scheme 2 or 3 from ISO/IEC 9796-2. However, it still makes sense to use $e=65537$:


The only known drawbacks are the performance loss (by a factor like 8), and the risk of leaving a bug in the key generator when a prime $p\equiv 1\pmod{65537}$ is hit; and when performance matters, there is an even better choice than $e=3$, with provable security (but more complex and uncommon).
Some attacks on less than perfect RSA schemes that are (or have been) in wide use are significantly harder than with $e=3$ (as discussed above).
$e=65537$ has become an industry standard (I have yet to find any RSA hardware of software that does not allow it), and is prescribed by some certification authorities.

