0
$\begingroup$

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

enter image description here

|improve this question
$\endgroup$
2
$\begingroup$

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
$\endgroup$
  • $\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.