2015/02/10 by Covanov, Svyatoslav, Thomé, Emmanuel
#Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Symbolic Computation (cs.SC)
paper · doi:10.48550/arxiv.1502.02800
For almost 35 years, Schönhage-Strassen's algorithm has been the fastest algorithm known for multiplying integers, with a time complexity O(n × log n × log log n) for multiplying n-bit inputs. In 2007, Fürer proved that there exists K > 1 and an algorithm performing this operation in O(n × log n × K log n). Recent work by Harvey, van der Hoeven, and Lecerf showed that this complexity estimate can be improved in order to get K = 8, and conjecturally K = 4. Using an alternative algorithm, which relies on arithmetic modulo generalized Fermat primes, we obtain conjecturally the same result K = 4 via a careful complexity analysis in the deterministic multitape Turing model.