# FFT multiplication for RLWE key exchange [closed]

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.<X> = PolynomialRing(Rq)
S.<x> = 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)

• Thanks for answer. What is negacyclic convolution and how it is different from normal convolution? – vivek Apr 27 '18 at 4:31
• The acyclic convolution (i.e., padding with zeroes up to twice the length and performing $\mathrm{FFT}^{-1}(\mathrm{FFT}(a) \ast \mathrm{FFT}(b))$), calculates the polynomial multiplication without reduction; the cyclic convolution computes $a\cdot b \bmod (X^n - 1)$; the negacyclic convolution computes $a \cdot b \bmod (X^n + 1)$. – Samuel Neves Apr 28 '18 at 2:36