Faster integer and polynomial multiplication using cyclotomic coefficient rings
[ Homepage | Publications | Talks | TeXmacs | Mathemagix ]


We present an algorithm that computes the product of two -bit integers in bit operations. Previously, the best known bound was . We also prove that for a fixed prime , polynomials in of degree may be multiplied in bit operations; the previous best bound was .

Authors: David Harvey, Joris van der Hoeven

View: Pdf, BibTeX