Understanding a method of vector multiplication
I can't completely answer your question, but I don't see how sage can't compute the polynomial multiplication - are you computing in the residue ring modulo $x^n + 1$?
The following executes within a few hundreds of milliseconds on my computer:
R.&lt;x&gt; = PolynomialRing(GF(2), &quot;x&quot;)
RR.&lt;z&gt; = R.quo(x^57367 + 1)
RR.random_element() * RR.random_element()

Maybe you can use this to debug your implementation.
Hope I could help!