Re:Factoring may be easier than we think (2016)
by jasonhansel on Sunday June 30, 2019 @01:06PM
(#20319176)
But what if you find an algorithm with a low asymptotic complexity, but with such a high constant factor that it could not be put into practical use? We would still want to move away from RSA (since constant factors can often be improved), but there would be no way to actually use the algorithm in its current form.
Re:Factoring may be easier than we think (2016)
by rocqua on Sunday June 30, 2019 @06:12PM
(#20320890)
In that case, there is no immediate threat when publishing. Unless you area afraid someone else can improve on the constant factor, this won't break crypto.
Re:Factoring may be easier than we think (2016)
by jasonhansel on Sunday June 30, 2019 @07:35PM
(#20321286)
> there is no immediate threat when publishing.
Unless someone else comes up with the same algorithm, and does lower the constant factor.
Re:Factoring may be easier than we think (2016)
by Ar-Curunir on Sunday June 30, 2019 @06:37PM
(#20321014)
Cryptography research moves very fast =)
Re:Factoring may be easier than we think (2016)
by archgoon on Sunday June 30, 2019 @02:13PM
(#20319557)
You might have discovered a fast algorithm that doesn't actually reduce the asymptotic complexity (just flattens it out for a larger initial space), or the asymptotic complexity isn't what you think it is.
This has little impact on what someone can do with the algorithm, but it sounds like the author is concerned with ensuring that they understand why their new algorithm works. Since they're committed to not discussing their discovery for several years, it seems reasonable to want to make sure they haven't convinced themselves of something that doesn't work the way they think.
I think my plan would just be to publish that factorisation anonymously (being super paranoid to avoid being traced) and then wait however long was necessary before publishing the algorithm.