FFT multiplication for RLWE key exchange I am try to multiply two  polynomial quotient ring of type $R=Z[x]/\phi(x) $ in sage using Fast Fourier Transform.:    

a=Rq.random_element()
R. = PolynomialRing(GF(40961))  # Gaussian field of integers
Y. = R.quotient(X^(dimension) + 1)   # Cyclotomic field
ouput=Y(a)*Y(a)

I have found the following code on github to do this job but it is for simple polynomials and when I run this code for quotient polynomial, It give me following Type error
Sage itself has an internal negacyclic convolution, which is what is necessary here. To avoid type errors, we convert the polynomials to lists of coefficients, and work with those instead:

from sage.rings.polynomial.convolution import _negaconvolution_fft

n = 10 # degree 1024
Rq = GF(40961)
R.&lt;X&gt; = PolynomialRing(Rq)
S.&lt;x&gt; = R.quotient_ring(X^(2^n) + 1)
u = S.random_element()
v = S.random_element()

w_1 = S(_negaconvolution_fft(list(u), list(v), n))
w_2 = u * v
assert(w_1 == w_2)