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

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

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

enter image description here


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)
|improve this answer|||||
  • $\begingroup$ Thanks for answer. What is negacyclic convolution and how it is different from normal convolution? $\endgroup$ – vivek Apr 27 '18 at 4:31
  • $\begingroup$ 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)$. $\endgroup$ – Samuel Neves Apr 28 '18 at 2:36

Not the answer you're looking for? Browse other questions tagged or ask your own question.