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[SUB]Q[/SUB] (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? 
[URL="https://math.stackexchange.com/questions/699638/whyafalsestatementcanimplyanything"]if pigs fly, then [/URL][URL="https://math.stackexchange.com/questions/699638/whyafalsestatementcanimplyanything"]1+1=3[/URL].

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

[QUOTE=tetramur;506551]A. Joux created in 2013 a new algorithm (index calculus, JIC) for finding a discrete logarithm with time complexity of L[SUB]Q[/SUB] (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.[/QUOTE] 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 RSA1024. 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. 
[QUOTE=Batalov;506583][URL="https://math.stackexchange.com/questions/699638/whyafalsestatementcanimplyanything"]if pigs fly, then [/URL][URL="https://math.stackexchange.com/questions/699638/whyafalsestatementcanimplyanything"]1+1=3[/URL].[/QUOTE]
No. An algorithm for DL implies algorithm for IF and vice versa. Look! Elliptic curves QS (only IF?) NFS IC (only DL?) [URL="https://crypto.stackexchange.com/questions/9385/reductionofintegerfactorizationtodiscretelogarithmproblem"]IF and DL are related.[/URL] 
[QUOTE=tetramur;506624]No. An algorithm for DL implies algorithm for IF and vice versa.[/QUOTE]
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. 
[QUOTE=jasonp;506590]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[/QUOTE]
Can method used by Joux et al. be extended with keeping time complexity the same? If yes, how can it be done? 
Doing that in general prime fields would imply breaking DiffieHellman. Predictions are tricky, especially about the future.

[QUOTE=jasonp;506636]Doing that in general prime fields would imply breaking DiffieHellman.[/QUOTE]
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. 
All times are UTC. The time now is 11:20. 
Powered by vBulletin® Version 3.8.11
Copyright ©2000  2021, Jelsoft Enterprises Ltd.