Suppose I have a polynomial $p(x)$, and a "modulus" polynomial $q(x)$ of degree $d$. I want to find two polynomials $r_1(x),r_2(x)$ of degree $\le d_1,d_2$ such that $$p(x) \equiv r_1(x) x^t + r_2(x) \pmod{q(x)}$$ Assume $d_1+d_2= d$, and that we are working over some finite field.

Given $p(x),q(x),d,d_1,d_2,t$, is there an algorithm to find $r_1(x),r_2(x)$ that meets the conditions above (if any exist)?

In the special case where $t=d_2$, this is handled by reducing $p(x)$ mod $q(x)$, but I'm wondering if there is an efficient algorithm for the more general case. One algorithm is to express the coefficients of $r_1(x),r_2(x)$ as unknowns, write down $n$ linear equations in terms of these $d_1+d_2$ unknowns, and then solve the resulting linear system; this will take $O(d^3)$ time. Is there a more direct solution exploiting that these are polynomials, perhaps one achieving faster performance, such as $O(d)$ time?

  • $\begingroup$ Well, FFT gives you are way to do that division faster than solving the system of equations. See here. $\endgroup$
    – plop
    Mar 2 at 22:46
  • $\begingroup$ @plop, yeah, I already know you can use FFT for division, and you can use division to solve the case $t=d_2$ efficiently, but that's not my question - my question is whether you can solve the general case (where $t>d_2$) efficiently. Do you have a way to do that with FFT? I currently can't see how to do that. $\endgroup$
    – D.W.
    Mar 3 at 0:35
  • $\begingroup$ Well, some cases there will be no solutions forced by the relations between the degrees $d_1,d_2,t,d$ and the degree $s$ of the remainder of $p$ modulo $q$. For example, if $d>d_1+t>d_2$, and $d_1+t>s$, then we can't have such $r_1$ of degree $d_1$. Before thinking further, let me ask, because the conditions $d_1+d_2\leq d$ and $r_1,r_2$ having degree exactly $d_1,d_2$ look bizarre. Is that really what you want? You don't want $r_1,r_2$ of degree at most $d_1,d_2$, or do you? $\endgroup$
    – plop
    Mar 3 at 1:18
  • $\begingroup$ Do I understand correctly that essentially you want to find a representation of $p(x)$ in basis $(1,\ldots,x^{d_2}, \ x^{t}, \ldots, x^{t + d_1}, q(x), x q(x), x^2 q(x), \ldots)$? $\endgroup$
    – user114966
    Mar 3 at 3:03
  • $\begingroup$ @plop, Sorry. you're right. I really want them to have degree at most $d_1,d_2$. Also, let's assume $d_1+d_2=d$, for simplicity. I edited the question. $\endgroup$
    – D.W.
    Mar 3 at 5:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.