An RSA public key is made of of two parts -- a 'modulus' and an 'exponent'. The modulus is the part you're thinking about -- very large, computed from your private key, hard to factor, etc. He is talking about the exponent part, which can indeed be very small (and the same everywhere event).

I was taught in a crypto class a few years ago that an algorithm commonly used to encrypt messages runs in time proportional to the number of 1 bits in the binary representation of e, thus a smaller e is better and so 3 (11) is a very good candidate efficiency-wise. Is this true in the real world?

To raise something to the 3rd power in modular math is done by computing:

    x² = x · x
    x³ = x · x²

In other words, two modular multiplications. I have grouped them like this because, to raise something to the 17th power in modular math is done by computing:

    x² = x · x
    x⁴ = x² · x²
    x⁸ = x⁴ · x⁴
    x¹⁶ = x⁸ · x⁸
    x¹⁷ = x · x¹⁶

So that's 5 multiplications. If the exponent is 2^m + 1, we can generalize to say that it requires m + 1 multiplications; 17 is 2^4 + 1 and thus requires 4 + 1.

Of course, we're a long way from that, even. To raise something to the 2¹⁶ + 1 = 65537 power requires 17 multiplications. When you see these times of 10.6 μs and 23.9 μs for these respectively, this means that the multiplication isn't really the bottleneck yet. Let us imagine that the multiplication needs to be initialized in a constant time, then we could say that:

    10.6 = 2 t + C
    23.9 = 17 t + C

Solving, I get that the constant overhead is 8.8 μs while the time t for a multiplication is just 0.9 μs or so. So the constant time is about 10 multiplications worth! We can then test this for the next case, e=2^32 + 1, which is listed as 42.7 μs, the linear fit above suggests 0.9*33 + 8.8 = 38.5, which is not too bad of an estimate. (I suspect that it starts to use the general exponentiation algorithm, which requires that you do some bitwise operations to figure out whether you multiply an accumulating variable; that control logic might make up the missing 4 μs.)

All of these have the same number of 1 bits. It runs in time proportional to the number of total bits in the binary representation of e, not just the 1 bits. Other than that you're mostly right -- in the real world there are evidently constants and perhaps some curvature when nonstandard exponents are used.

Not quite, the cost of RSA encryption is O(k^3), where k is the total number of bits, not the number of 1's. But it is cheaper to have less 1 bits, as (abusing big-O notation), the cost is more like O(3k^3-z^3), where z is the number of 0 bits. That's why some people are using 2^32+1 instead of 2^32-1.

In theory the size of e doesn't matter, but a larger e does make it harder to brute force the message text.

You're mixing up the number of bits in the RSA modulus n, and the number of bits in the exponent e.

Integer modular multiplication is O(n^2)[1]. Binary exponentiation, the most common of algorithms, requires O(e) modular multiplications. It is therefore trivial to get to the O(n^3) figure of general modular exponentiation.

RSA encryption with e = 3 is much simpler, consisting of exactly 2 modular multiplications. That makes it O(n^2).

Note that an exponent with very low hamming weight can still be O(n^3). For example e = 2^(n-1) + 1 requires n multiplications, therefore O(n^3).

[1] If you want to go all theoretical, it can be as low as O(n log n log log n) using Schoenhage-Strassen. But that is not practical for 1024--4096 bit integers.

Those are values. 2^16+1 bits would be a very big number.

Not anywhere near big enough to be cryptographically secure. RSA uses 2 numbers as the public key, e and n. n should be more than 1024 bits, and it really doesn't matter how big e is. The default for e for a while (and cryptographically secure in theory) was 3 because computing y=x^3 mod n (aka RSA encryption) was cheap. What matters in RSA though is n being large and hard to factor, not in e being large.

EDIT: my bad, I misread the "2^16+1 bits" as 2^16+1 every time I read it.

While you are correct, it looks to me like tedunangst thought the numbers should have a bit length of 65,537 bits. That frakken huge. And not at all what this article says.

He said "2^16+1 bits would be a very big number." That's 65,537 bits.

Actually, I'm saying it is not the bit length. But that seems to be the interpretation of the original comment.

2^16 is significantly larger than 1024.

To clarify, I meant to write "default maximum size". (and thus ceiling of log_2 of that being the max bit size). That aside, down voting my voicing a reasonable question which spurred a subthread that has useful dialogue seems a bit immature.