Where is a new fast algorithm of factorization?
A. Joux created in 2013 a new algorithm (index calculus, JIC) for finding a discrete logarithm with time complexity of L_{Q} (1/4, c) for c > 0. Can we find an algorithm for integer factorization with the same time complexity, using JIC?
If yes, then for RSA1024 it would be several billions times better than GNFS. We have:
GNFS will have aprx. 1.4*10^26 operations.
JIC will have aprx. 5*10^17 operations for c = (64/9)^(1/3), same c as GNFS.
If c = 1, then we will have only 1.6*10^9 operations (!)...
For RSA2048:
GNFS
1.61*10^35 operations
JIC, c = (64^9)/(1/3)
4.79*10^22 operations (!)
JIC, c = 1
6.22*10^11 operations (!!)
Is it amazing?
Last fiddled with by tetramur on 20190121 at 11:22
