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