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?

Advertisements