88 citations · 270 across the 33 of their papers we have counts for
Showing 2017 · cs.SCShow all
2 papers · 2 filters
cs.SC2017★ 7 cited
Faster integer and polynomial multiplication using cyclotomic coefficient rings
David Harvey, Joris van der Hoeven
We present an algorithm that computes the product of two n-bit integers in O(n log n (4\sqrt 2)^{log^* n}) bit operations. Previously, the best known bound was O(n log n 6^{log^* n…
cs.SC2017
Faster truncated integer multiplication
David Harvey
We present new algorithms for computing the low bits or the high bits of the product of two -bit integers. We show that these problems may be solved in asymptotically 75…