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
DOI: https://doi.org/10.1090/mcom/3328
Published electronically: April 11, 2018
Full-text PDF

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
Email: d.harvey@unsw.edu.au

Joris van der Hoeven
Affiliation: CNRS, Laboratoire d’informatique, UMR 7161 CNRS, École polytechnique, 91128 Palaiseau, France
Email: vdhoeven@lix.polytechnique.fr

DOI: https://doi.org/10.1090/mcom/3328
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

American Mathematical Society