Follow

Breaking news in the algorithmic/arithmetic world!

Integer multiplication in time O(n · log n). [1]

It means you can multiply two n-bits integer using roughly n log n operations. It's a *very* important problem because a lot of mathematical software rely on efficient integer multiplication.

It breaks the last best known algorithm [2] (Schönhage–Strassen), that was in O(n · log n · log log n)

[1] https://hal.archives-ouvertes.fr/hal-02070778/document

[2] https://en.wikipedia.org/wiki/Sch%C3%B6nhage%E2%80%93Strassen_algorithm

@erou

But, most importantly, this asymptotic can ve memorized more easily!…

And, if seriously, one question right away: what about hardware, can it be translated into the number of gates?

@amiloradovsky

I have no idea, this is something I know nothing about, sorry! 😅

"The main results of this paper also hold in the Boolean circuit model [40, Sec. 9.3], with essentially the same proofs." 👍

@erou neat!!!

@erou log log n is practically 1, tho :-P

I wonder how the coefficients compare for actual uses.

@varx

Yep that's still an open question. In the paper they explicitly say that they were interested in the theoretical complexity!

Go on and make the comparisons 😎!

@erou

>breaking

I'm just glad it doesn't break any crypto.

Depending on the actual practical efficiency of the algorithm, it could help to break some factorization or discrete logarithms records I guess!

It's a speedup of log log n.

For n = 2^4096, log n = 4096, n = 12.

Getting 12 times faster is fortunately not a significant threat. I bet you could get this much speedup, or more, by eg. switching from general-purpose computers to ASICs.

@Wolf480pl A factor 12 is a big deal when you need years of computations, it saves you a lot of money/time/electricty. Also, the constant hiding in the big O notation could potentially be smaller in O(n log n) than in the previous O (n log n log log n), making the speedup even greater.

I am not saying that it is sufficient to break cryptosystems though, the gap is too huge for that!

@Wolf480pl Well the O(n log n) algorithm was surprising in itself.

At this point the practicality of the algorithm is still unknown, so we can only speculate 🙂

redbird@redbird@lor.sh@erou Wow!