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)


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?

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

@erou Seems like it can:
"The main results of this paper also hold in the Boolean circuit model [40, Sec. 9.3], with essentially the same proofs." 👍

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

I wonder how the coefficients compare for actual uses.

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


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!

@erou no.
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!

@erou meh, I'd be surprised if the constant in big O was smaller. The O(n log n) algorithm probably has bigger constant than the O(n log n log log n) one.

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

Sign in to participate in the conversation

A Mastodon instance for maths people. The kind of people who make \(\pi z^2 \times a\) jokes.

Use \( and \) for inline LaTeX, and \[ and \] for display mode.