# Integer Multiplication in NlogN Time

*A win for multi-variable polynomials*

Composite crop from src1, src2 |

David Harvey and Joris van der Hoeven are computational mathematicians. They have just released a paper showing how to multiply two -bit integers in time. A companion paper gives details of a simpler second algorithm that is time pending a widely-believed conjecture about primes.

Today we discuss what makes these new results possible.

The first paper leads off with a nice history of algorithms that beat the -time method all of us learned in school. Far from being galactic, the longtime-champion algorithm of Arnold Schönhage and Volker Strassen is a workhorse of the GNU Multiple Precision Library (GMP). The factor was improved by Martin Fürer in 2007 and further in 2014 by Harvey and van der Hoeven with Grégoire Lecerf. Now it is gone altogether.

Their algorithm is currently not practical, but it is also not yet tuned. At the start of section 5, they note that their estimates take effect for where they use . When they note that they don’t mean the numbers need at least bits, rather is the number of bits. Since there are only about particles in the observable universe, this puts the term galactic to shame.

The number recalls a famous story about Godfrey Hardy and Srinivasa Ramanujan. This is not wholly a coincidence. They get a bounding multiplier of from one place, another factor of from another, and finally a factor of giving which equals . Then they just make be higher by , setting up which happens to equal . But there is much flex in the choices and they sketch how to improve the needed bound from to just . They also uncover some new tricks for calculating in certain large finite rings defined via multi-variable polynomials.

## Polynomials and Tricks

When we heard the news on Tuesday, both of us thought of the famous primality test of Manindra Agrawal, Neeraj Kayal, and Nitin Saxena (AKS), which placed deciding primality into deterministic polynomial time. We stated the message as the title of an old post on other joint work by Kayal: “Polynomials Are Easier Than Integers.”

The crux of the AKS test is to employ the theorem that for any co-prime , the polynomial congruence relation

holds in if and only if is prime. This is tested in the quotient ring . The game becomes finding small enough and minimizing the number of that need to be checked in order for the body of tests in the quotient ring to be conclusive.

We take time to note that the case is possibly sufficient while testing a small set of . Agrawal has conjectured that if modulo both and then either is prime or divides . This conjecture is doubted on heuristic counting grounds but it has been verified for and can be modified by including the case . It would improve the polynomial time in the number of bits in from to and also improve the constants. We mention this because Harvey and van der Hoeven have a number-theoretic conjecture that (as shown in their companion paper) improves both their constant on and the simplicity of the proof.

The further message of the new papers is added power from giving the polynomials more variables. They use variables: plus a nominal that is later substituted by . Here is a certain power of and combined with the -th variable to build the base ring of complex polynomials in modulo . The other variables are used to mod out by where the are powers of no higher than . Operations in quotient rings of this type are especially efficient. They are used to emulate operations in where is a product of primes that are near powers of . The emulation is done via the isomorphism

which follows from the Chinese remainder theorem.

They start with Schönhage and Strassen’s original trick of splitting the two -bit integers into -sized pieces so that the problem reduces to multiplying polynomials of degree in with coefficients of size. They use the -dimensional Discrete Fourier Transform over with complex operations that need only bits of precision individually. This setting also gives leeway for approximative methods in their final algorithm. But first we describe what was evidently their original strategy.

## The Recursive Strategy

Their first task in either case is to find -many distinct primes of order in magnitude. Now when the exponent makes the primes quite small indeed, and the need to find distinct ones already drives up quite high before their algorithm can even go into effect. Moreover, for the approximation to work, the primes need to be congruent to modulo .

Their original strategy—detailed in the companion paper—builds on a result of Charles Rader to reduce the DFT computation to multiplications in

where compared to (1) they have reduced the exponents by one. Using , they next reduce this to multiplications in

Then the above-mentioned substitution of by makes them into products over

These last products are at last amenable to the usual Fast Fourier Transform trick of applying FFT for each by pretending that is a primitive -th root of unity, multiplying pointwise in , and doing the inverse FFT. Finally the products in can be converted into -bit integer products, and this sets up the vast recursion from multiplying the original -bit integers to a batch of -bit ones.

## Finding Good Primes

In order for the recursion to solve to , they need the values to be not too large. Viewing this task from the bottom up, they want to choose a single value and choose small such that is prime. Since is a power of , there is some resemblance to the harder task of finding Sophie Germain primes, which are also relevant to the AKS algorithm. In this case, however, all they need is a sufficiently small such that:

For all coprime with sufficiently large, there is a prime such that .

This is, however, only known for “” and the Generalized Riemann Hypothesis is only known to improve the bound to for any . The above is conjectured to hold for any but it hasn’t been proved. They currently need it for .

The companion paper uses the conjecture to improve multiplication in the field to time . This uses a single algorithm over any prime and power ; of course if they are fixed, then this time likewise becomes . This currently needs .

The companion paper has full details of how all this works and many more numerical tricks than we’ve mentioned—a *tour de force*. Getting the result for integer multiplication unconditionally, however, requires one more major tool in their arsenal. To use it they set up the primes to be slightly below respective powers of 2 (rather than be above a single power of by the aforementioned factors ) while retaining .

Their innovation compared to the translations in the first strategy is that one can still reduce the DFT computation in dimensions needing precision to a complex DFT in dimensions by employing approximation. Their algorithm is completely deterministic but it employs weights that conform to Gaussian distributions to effect the approximation. The preservation of Gaussians under Fourier transforms enables close enough approximations to be obtained by solving relatively small and easily-specified systems of linear equations. The resulting complex DFT is then massaged in a manner similar to the first strategy. The resulting recursion is not quite as steep—it goes from to —but it gives

with and the term independent of (indeed, becomes the aforementioned ). This gives . The approximation technique does not work for multiplication in , however. As usual, here is where we say to consult the papers for further details—there is a wealth of them.

## Open Problems

Will the time be concretely improvable? Will it tell us anything about the problem of proving a super-linear lower bound? And short of those two goals, what new results will become possible through the multi-variable polynomial techniques they employ?

### Trackbacks

- 10 Milestones in the History of Mathematics according to Nati and Me | Combinatorics and more
- The Breakthrough Result Of 2019 | Gödel's Lost Letter and P=NP
- Shtetl-Optimized » Blog Archive » Wonderful world
- Network Coding Yields Lower Bounds | Gödel's Lost Letter and P=NP
- Novedades sobre la multiplicación – Blog del Instituto de Matemáticas de la Universidad de Sevilla
- Dyson as a Mathematician | Gödel's Lost Letter and P=NP
- Predictions For 2021 | Gödel's Lost Letter and P=NP

Well, the O(n log n) upper bound won’t be improved without refuting a central conjecture in network coding 🙂

https://arxiv.org/abs/1902.10935

Highly interesting, thanks!

The P versus NP problem is a major unsolved problem in computer science. This is considered by many to be the most important open problem in the field. If any single NP-complete problem can be solved in polynomial time, then every NP problem has a polynomial time algorithm. We prove the known NP-complete problem BETWEENNESS can be solved in polynomial time. We also provide a Computer Code and Software which decides the instances of this problem in polynomial time.

The proof and code is in GitHub Inc:

https://github.com/frankvegadelgado/P-NP

Thanks in advance!!!

I made my first release of the solution of the NP-complete problem BETWEENNES on GitHub Inc. and I uploaded the binary so you could test it without the compilation of the source and report any error or check some examples.

Here is the release:

https://github.com/frankvegadelgado/P-NP/releases/tag/betweenness-1.0

Thanks in advance!!!

After a feedback of some researchers, I found a bug in the first pre-release. I tried to fix it and I think I could do it. I want to thank you all for your advice after reading these comments and my emails. The new solution is released in

https://github.com/frankvegadelgado/P-NP/releases/tag/betweenness-1.1

and fixes the problem of transitivity that must require a solution. Since this step was missing in the first release there were No instances that output Yes by the program. After I fixed the problem and tested again, then this works fine this time.

Thanks in advance!!!

We are still improving the code and the theoretical proof after the feedback of some good people who have approach to help. Thanks to them, I have a new version improved in the pre-release betweenness-1.3 in

https://github.com/frankvegadelgado/P-NP/releases/tag/betweenness-1.3

Any comment or advice are always welcome.

Thanks in advance!!!

I finally made my first release. This is a resume of previous pre-release. In addition, we consolidate in this version the solution with more technical arguments which support the evidence this polynomial time algorithm actually works…(Besides, we implement those technical improvements)

It is good to share you

https://github.com/frankvegadelgado/P-NP/releases/tag/betweenness-1

Thank you very much!!!

The problem in these algorithms is the target is ‘all’ the output for x^2 while entropy of output remains O(t) if |x|<=2^t and the logic can be framed without quantifiers.

‘entropy of output remains $\leq t$’.