Where is a new fast algorithm of factorization?

tetramur · 2019-01-21, 11:21

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 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?

Batalov · 2019-01-21, 17:05

if pigs fly, then 1+1=3.

jasonp · 2019-01-21, 18:34

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

CRGreathouse · 2019-01-22, 01:38

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 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 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.

tetramur · 2019-01-22, 05:40

Quote:

Originally Posted by Batalov

if pigs fly, then 1+1=3.

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.

CRGreathouse · 2019-01-22, 05:49

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.

tetramur · 2019-01-22, 07:36

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?

jasonp · 2019-01-22, 12:09

Doing that in general prime fields would imply breaking Diffie-Hellman. Predictions are tricky, especially about the future.

CRGreathouse · 2019-01-22, 14:50

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.

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 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 RSA-1024 it would be several billions times better than GNFS. We have: GNFS will have aprx. 1.410^26 operations. JIC will have aprx. 510^17 operations for c = (64/9)^(1/3), same c as GNFS. If c = 1, then we will have only 1.610^9 operations (!)... For RSA-2048: GNFS 1.6110^35 operations JIC, c = (64^9)/(1/3) 4.7910^22 operations (!) JIC, c = 1 6.2210^11 operations (!!) Is it amazing? Last fiddled with by tetramur on 2019-01-21 at 11:22

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	2019-06-14 03:13
amorosi - new fast factorization not deterministic	Alberico Lepore	Alberico Lepore	5	2018-01-19 11:38
18th Test of primality and factorization of Lepore in 5 * log_25 (N) (New Year's algorithm)	Alberico Lepore	Alberico Lepore	2	2018-01-01 21:31
new factorization algorithm	jasonp	Math	2	2012-06-17 20:04
Fast factorization method or crankery?	10metreh	Factoring	6	2010-04-08 11:51

2019-01-21, 17:05	#2
Batalov "Serge" Mar 2008 Phi(4,2^7658614+1)/2 3×5²×131 Posts	if pigs fly, then 1+1=3.

2019-01-21, 18:34	#3
jasonp Tribal Bullet Oct 2004 5·709 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, 12:09	#8
jasonp Tribal Bullet Oct 2004 5×709 Posts	Doing that in general prime fields would imply breaking Diffie-Hellman. Predictions are tricky, especially about the future.