[ Homepage | Publications | Talks | TeXmacs |
Mathemagix ] |

Let denote the bit complexity of multiplying -bit integers, let be an exponent for matrix multiplication, and let be the iterated logarithm. Assuming that and that is increasing, we prove that matrices with -bit integer entries may be multiplied in

bit operations. In particular, if is large compared to , say , then the complexity is only .

**Authors:**

**Keywords: **matrix multiplication, complexity, algorithm,
FFT, Bluestein reduction

**A.M.S. subject classification: **68W30, 68Q17, 68W40