88 citations · 270 across the 33 of their papers we have counts for
9 papers · 1 filter
Faster integer multiplication using short lattice vectors
David Harvey, Joris van der Hoeven
We prove that -bit integers may be multiplied in bit operations. This complexity bound had been achieved previously by several authors, assuming va…
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…
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…
Faster integer multiplication using plain vanilla FFT primes
David Harvey, Joris van der Hoeven
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.
Faster arithmetic for number-theoretic transforms
David Harvey
We show how to improve the efficiency of the computation of fast Fourier transforms over F_p where p is a word-sized prime. Our main technique is optimisation of the basic arithmet…
Faster exponentials of power series
David Harvey
We describe a new algorithm for computing exp(f) where f is a power series in C[[x]]. If M(n) denotes the cost of multiplying polynomials of degree n, the new algorithm costs (2.16…