Faster truncated integer multiplication

DOI10.1090/MCOM/3939arXiv1703.00640OpenAlexW2594368247MaRDI QIDQ6203462FDOQ6203462

Authors: David Harvey 

Publication date: 28 February 2024

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

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.

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

Mathematics Subject Classification ID

Symbolic computation and algebraic computation (68W30)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Modern computer arithmetic
• Title not available (Why is that?)
• Modular Multiplication Without Trial Division
• Even faster integer multiplication
• The Fast Fourier Transform in a Finite Field
• On short multiplications and divisions
• The truncated fourier transform and applications
• Integer multiplication in time \(O(n\log n)\)
• Lagrange inversion
• Faster integer multiplication using short lattice vectors

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)