20190121, 11:21  #1 
"unknown"
Jan 2019
anywhere
17 Posts 
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 
20190121, 17:05  #2 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
9,613 Posts 

20190121, 18:34  #3 
Tribal Bullet
Oct 2004
3·1,181 Posts 
Nobody knows if there is a way to transfer the recent improvements in discrete logarithms to the integer factorization domain. Note that the kind of discrete logs that can be solved quickly by Joux et al would not appear in actual cryptosystems

20190122, 01:38  #4  
Aug 2006
3·1,993 Posts 
Quote:


20190122, 05:40  #5  
"unknown"
Jan 2019
anywhere
17 Posts 
Quote:
Elliptic curves QS (only IF?) NFS IC (only DL?) IF and DL are related. 

20190122, 05:49  #6 
Aug 2006
3·1,993 Posts 
A general algorithm for discrete logarithms implies an algorithm for integer factorization. But Joux's algorithm isn't general, and so it doesn't directly give rise to a factorization algorithm. It wouldn't be surprising if it did give a factorization algorithm for an appropriatelyrestricted setting, but it's not at all clear what that would look like, and it probably wouldn't be naturallooking in the integers. Personally I think that it would be worth a paper to do this (and such a paper would likely include an actual factorization). But this is outside my expertise, so I won't be the one writing that paper.

20190122, 07:36  #7 
"unknown"
Jan 2019
anywhere
17_{10} Posts 
Can method used by Joux et al. be extended with keeping time complexity the same? If yes, how can it be done?

20190122, 12:09  #8 
Tribal Bullet
Oct 2004
3·1,181 Posts 
Doing that in general prime fields would imply breaking DiffieHellman. Predictions are tricky, especially about the future.

20190122, 14:50  #9 
Aug 2006
3×1,993 Posts 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Whats is a fast algorithm for compute znorder(Mod(2,p)).  JM Montolio A  Miscellaneous Math  10  20190614 03:13 
amorosi  new fast factorization not deterministic  Alberico Lepore  Alberico Lepore  5  20180119 11:38 
18th Test of primality and factorization of Lepore in 5 * log_25 (N) (New Year's algorithm)  Alberico Lepore  Alberico Lepore  2  20180101 21:31 
new factorization algorithm  jasonp  Math  2  20120617 20:04 
Fast factorization method or crankery?  10metreh  Factoring  6  20100408 11:51 