4 ms·
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
by 30thElement 15y ago
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.
- pbsd 15y agoYou'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.