Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



Faster integer multiplication using plain vanilla FFT primes

Authors: David Harvey and Joris van der Hoeven
Journal: Math. Comp. 88 (2019), 501-514
MSC (2010): Primary 68W30, 68W40, 11Y16
Published electronically: April 11, 2018
Full-text PDF
View in AMS MathViewer New

Abstract | References | Similar Articles | Additional Information

Abstract: Assuming a conjectural upper bound for the least prime in an arithmetic progression, we show that $ n$-bit integers may be multiplied in $ O(n \log n\, 4^{\log ^* n})$ bit operations.

References [Enhancements On Off] (What's this?)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 68W30, 68W40, 11Y16

Retrieve articles in all journals with MSC (2010): 68W30, 68W40, 11Y16

Additional Information

David Harvey
Affiliation: School of Mathematics and Statistics, University of New South Wales, Sydney NSW 2052, Australia

Joris van der Hoeven
Affiliation: CNRS, Laboratoire d’informatique, UMR 7161 CNRS, École polytechnique, 91128 Palaiseau, France

Received by editor(s): November 28, 2016
Received by editor(s) in revised form: September 25, 2017
Published electronically: April 11, 2018
Additional Notes: The first author was supported by the Australian Research Council (grants DP150101689 and FT160100219).
Article copyright: © Copyright 2018 David Harvey and Joris van der Hoeven