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] hal.archives-ouvertes.fr/hal-0
[2] en.wikipedia.org/wiki/Sch%C3%B

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

@erou
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! 😅

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

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

@Wolf480pl
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
Mathstodon

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.