View Single Post
Old 2019-01-21, 11:21   #1
tetramur
 
"unknown"
Jan 2019
anywhere

100012 Posts
Default 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 LQ (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 RSA-1024 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 RSA-2048:
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 2019-01-21 at 11:22
tetramur is offline   Reply With Quote