Polynomial multiplication using the DFT?

savecancel

Here is the example from the article in SageMath:

sage: R.<x> = PolynomialRing(QQ)
sage: f = 1 + x
sage: g = 1 + x + x^2
sage: fg_deg = f.degree() + g.degree()
sage: I_f = IndexedSequence([f.monomial_coefficient(x^d) for d in range(fg_deg+1)], list(range(fg_deg+1)))
sage: I_g = IndexedSequence([g.monomial_coefficient(x^d) for d in range(fg_deg+1)], list(range(fg_deg+1)))
sage: I_fg = IndexedSequence(list(vector(I_f.dft().list()).pairwise_product(vector(I_g.dft().list()))), list(range(fg_deg+1))).idft()
sage: fg = sum(c*x^k for k,c in I_fg.dict().items())
sage: fg == f*g
True