Faster truncated integer multiplication

DOI10.1090/MCOM/3939MaRDI QIDQ6203462zbMATH OpenOpenAlexFDO

Authors David Harvey

Publication date 28 February 2024

Published in Mathematics of Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1703.00640

Mathematics Subject Classification ID

Symbolic computation and algebraic computation (68W30)

Abstract: We present new algorithms for computing the low n bits or the high n bits of the product of two n-bit integers. We show that these problems may be solved in asymptotically 75% of the time required to compute the full 2n-bit product, assuming that the underlying integer multiplication algorithm relies on computing cyclic convolutions of real sequences.

Cites work

• scientific article; zbMATH DE number 1268810 (Why is no real title available?)
• scientific article; zbMATH DE number 610968 (Why is no real title available?)
• scientific article; zbMATH DE number 976329 (Why is no real title available?)
• Even faster integer multiplication
• Faster integer multiplication using short lattice vectors
• Integer multiplication in time \(O(n\log n)\)
• Lagrange inversion
• Modern computer arithmetic
• Modular Multiplication Without Trial Division
• On short multiplications and divisions
• The Fast Fourier Transform in a Finite Field
• The truncated fourier transform and applications

This page was built for publication: Faster truncated integer multiplication

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6203462)