Recently, I am working on polynomial division. Suppose coefficients of all polynomials are elements in $GF(2^q)$. I want to calculate the remainder such that
$f(x) = g(x)q(x) + r(x)$ (1)
I searched a lot, and one algorithm draws my attention is the one in the following link
http://people.csail.mit.edu/madhu/ST12/scribe/lect06.pdf
The key idea is as below:
Let the $Rev$ denotes reciprocal of a polynomial (reverse order of the coefficient). Then one can obtain
$Rev(q) = Rev(g)^{-1}Rev(f)~~$mod$~~x^{deg(f) - deg(g)}$ (2)
where $Rev(g)^{-1}$ is defined as
$Rev(g)^{-1}Rev(g) = 1$ mod $x^{deg(g)+1}$
Then $r(x)$ can be obtained by substitute $q(x)$ back to the equation (1). If one follows this algorithm, he or she needs to multiply twice. Once at equation (2) and once at equation (1).
However, since I am only interested in $r(x)$. Also, my application scenario is that I have a lot of $f(x)$ needs to be divided by the same $g(x)$. Therefore, is there anyway I can "substitute" (2) into (1) to get only one equation such that only one multiplication is needed (other multiplications can be precalculated since $g(x)$ is the same). I tried to do that, yet I failed. It is mostly because there is non-linear operation "mod" in (2) so that linearity does not hold anymore.
Thanks
There appears to exist something called a Number Theoretic Transform (NTT) which should have the properties of a Discrete Fourier Transform (DFT), one of which is that it turns convolution into multiplication. As (I assume) polynomial multiplication for finite fields also are convolution of their coefficients if "fast" / factored versions of the NTT exist these should provide speed-ups at least for multiplying / dividing high-order polynomials.