mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Factoring (https://www.mersenneforum.org/forumdisplay.php?f=19)
-   -   Where is a new fast algorithm of factorization? (https://www.mersenneforum.org/showthread.php?t=24020)

 tetramur 2019-01-21 11:21

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

[URL="https://math.stackexchange.com/questions/699638/why-a-false-statement-can-imply-anything"]if pigs fly, then [/URL][URL="https://math.stackexchange.com/questions/699638/why-a-false-statement-can-imply-anything"]1+1=3[/URL].

 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=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 RSA-1024 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 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=Batalov;506583][URL="https://math.stackexchange.com/questions/699638/why-a-false-statement-can-imply-anything"]if pigs fly, then [/URL][URL="https://math.stackexchange.com/questions/699638/why-a-false-statement-can-imply-anything"]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/reduction-of-integer-factorization-to-discrete-logarithm-problem"]IF and DL are related.[/URL]

 CRGreathouse 2019-01-22 05:49

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

 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=jasonp;506636]Doing that in general prime fields would imply breaking Diffie-Hellman.[/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 18:59.