FFT multiplication for RLWE key exchange
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)