mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2019-01-21, 11:21   #1
tetramur
 
"unknown"
Jan 2019
anywhere

17 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
Old 2019-01-21, 17:05   #2
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

59·163 Posts
Default

if pigs fly, then 1+1=3.
Batalov is offline   Reply With Quote
Old 2019-01-21, 18:34   #3
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

354310 Posts
Default

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
jasonp is offline   Reply With Quote
Old 2019-01-22, 01:38   #4
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

3×1,993 Posts
Default

Quote:
Originally Posted by tetramur View Post
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.
CRGreathouse is offline   Reply With Quote
Old 2019-01-22, 05:40   #5
tetramur
 
"unknown"
Jan 2019
anywhere

17 Posts
Default

Quote:
Originally Posted by Batalov View Post
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.
tetramur is offline   Reply With Quote
Old 2019-01-22, 05:49   #6
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

597910 Posts
Default

Quote:
Originally Posted by tetramur View Post
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.
CRGreathouse is offline   Reply With Quote
Old 2019-01-22, 07:36   #7
tetramur
 
"unknown"
Jan 2019
anywhere

1116 Posts
Default

Quote:
Originally Posted by jasonp View Post
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?
tetramur is offline   Reply With Quote
Old 2019-01-22, 12:09   #8
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

DD716 Posts
Default

Doing that in general prime fields would imply breaking Diffie-Hellman. Predictions are tricky, especially about the future.
jasonp is offline   Reply With Quote
Old 2019-01-22, 14:50   #9
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

175B16 Posts
Default

Quote:
Originally Posted by jasonp View Post
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.
CRGreathouse is offline   Reply With Quote
Reply

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

All times are UTC. The time now is 22:05.


Fri Dec 3 22:05:28 UTC 2021 up 133 days, 16:34, 0 users, load averages: 1.44, 1.48, 1.42

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

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.