arXiv Analytics

Sign in

arXiv:1703.00640 [cs.SC]AbstractReferencesReviewsResources

Faster truncated integer multiplication

David Harvey

Published 2017-03-02Version 1

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.

Related articles:
arXiv:1712.03693 [cs.SC] (Published 2017-12-11)
Faster integer and polynomial multiplication using cyclotomic coefficient rings
arXiv:1611.07144 [cs.SC] (Published 2016-11-22)
Faster integer multiplication using plain vanilla FFT primes