mersenneforum.org Where is a new fast algorithm of factorization?
 Register FAQ Search Today's Posts Mark Forums Read

 2019-01-21, 11:21 #1 tetramur   "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 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
 2019-01-21, 17:05 #2 Batalov     "Serge" Mar 2008 Phi(4,2^7658614+1)/2 59×163 Posts
 2019-01-21, 18:34 #3 jasonp 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
2019-01-22, 01:38   #4
CRGreathouse

Aug 2006

3×1,993 Posts

Quote:
 Originally Posted by tetramur 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.
Joux's algorithm, as I understand it, is more like an analogue of SNFS than GNFS. Probably there is an associated factorization algorithm but surely it would not apply to RSA-1024. My uneducated guess is that it would not apply to any numbers except those specially engineered for it. I'd love to hear from those more familiar with it.

2019-01-22, 05:40   #5
tetramur

"unknown"
Jan 2019
anywhere

100012 Posts

Quote:
 Originally Posted by Batalov
No. An algorithm for DL implies algorithm for IF and vice versa. Look!
Elliptic curves
QS (only IF?)
NFS
IC (only DL?)
IF and DL are related.

2019-01-22, 05:49   #6
CRGreathouse

Aug 2006

3×1,993 Posts

Quote:
 Originally Posted by tetramur No. An algorithm for DL implies algorithm for IF and vice versa.
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 appropriately-restricted setting, but it's not at all clear what that would look like, and it probably wouldn't be natural-looking 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.

2019-01-22, 07:36   #7
tetramur

"unknown"
Jan 2019
anywhere

1116 Posts

Quote:
 Originally Posted by jasonp 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
Can method used by Joux et al. be extended with keeping time complexity the same? If yes, how can it be done?

 2019-01-22, 12:09 #8 jasonp Tribal Bullet     Oct 2004 3×1,181 Posts Doing that in general prime fields would imply breaking Diffie-Hellman. Predictions are tricky, especially about the future.
2019-01-22, 14:50   #9
CRGreathouse

Aug 2006

3·1,993 Posts

Quote:
 Originally Posted by jasonp Doing that in general prime fields would imply breaking Diffie-Hellman.
Not to mention that working in prime fields would be to cut out the living, beating heart of Joux et al., which relies heavily on working in a 'small' characteristic.

 Similar Threads Thread Thread Starter Forum Replies Last Post JM Montolio A Miscellaneous Math 10 2019-06-14 03:13 Alberico Lepore Alberico Lepore 5 2018-01-19 11:38 Alberico Lepore Alberico Lepore 2 2018-01-01 21:31 jasonp Math 2 2012-06-17 20:04 10metreh Factoring 6 2010-04-08 11:51

All times are UTC. The time now is 23:27.

Sat Dec 4 23:27:14 UTC 2021 up 134 days, 17:56, 1 user, load averages: 0.82, 1.09, 1.12

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.