Effect of $L_n[1/4,c]$ integer factorization on RSA-2048

Question

Using the L-notation, integer factorization of an integer $n$ has the best known complexity of $L_n[1/3,c]$ using general number field sieve. Would discovery of an algorithm with complexity $L_n[1/4,c]$ be of any consequential significance to security of RSA-2048? If my computation is correct, for $c \approx 2$, it shows the complexity is reduced from $10^{36}$ to $10^{23}$, which seems doable with today's hardware. But I'm not confident in my computation or my assumptions about the capabilities of today's hardware.

Edit: here are my computations and assumptions: $\log(2^{2048})\approx1420$. $L_n[1/3,2]\approx \exp [2 (1420)^{1/3} (\log 1420)^{^{1 - 1/3}}]\approx 10^{36}$. $L_n[1/4,2]\approx \exp [2 (1420)^{1/4} (\log 1420)^{^{1 - 1/4}}]\approx 10^{23}$. Assuming $10^9$ possibilities can be tested every second and there are $10^6$ such processing units, it takes 3 years to crack RSA-2048: $10^{23} / (10^{9}\cdot60\cdot60\cdot24\cdot365)\approx 3 \times 10^6$.

Answer 1

Let's first quickly recap what $L_n[\alpha,c]$ actually means.

$$L_n[\alpha,c]=e^{(c+o(1))(\ln n)^{\alpha}(\ln\ln n)^{1-\alpha}}$$

$o(1)$ hides a constant (implementation and platform dependent) factor. For the rest of my answer I'll have to assume that the hidden factor is the same for the GNFS and the hypothetical $L_n[\alpha,c]$ algorithm (i.e. derived from $L_{2^{2048}}[1/3,(64/9)^{1/3}]=2^{112} \Rightarrow o(1)\approx -0.08035$).

In the next step you just plug-in your values for $\alpha$ and $c$ and get the result, for $\alpha=1/4$, this is:

$$L_{2^{2048}}[1/4,(64/9)^{1/3}]\approx 2^{72.15}$$

So if the algorithm is similarly fast (in terms of $c$ and hidden factors) it would reduce the security of 2048-bit RSA from roughly 112-bit to 72-bit which is considered borderline breakable (for nation states) right now.

Much more interesting though is the question how long would a modulus need to be in order to provide the same 112-bit security RSA-2048 did. This would ramp up the modulus length from 2048 to 7319 bits (!). And for 128-bit security you'd roughly need 10,891 bits instead of the roughly 3072 bits (extrapolation above would give 2800) right now.

Answer 2

Unfortunately, deriving actual numbers from asymptotic bounds makes little sense (after all, $10^{36}$ and $10^{23}$ are both $O(1)$). Getting an idea of the actual cost of running an algorithm requires a fine analysis of the algorithm itself; asymptotic results are not sufficient. An $L_n[1/4]$ algorithm for factoring would be a great theoretical result, but it wouldn't necessarily perform better than the current algorithms on, say, RSA-2048.

Fear the hidden constant factors.