# Express polynomial as sum of two lower-degree polynomials, modulo another

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?

• Well, FFT gives you are way to do that division faster than solving the system of equations. See here.
– plop
Mar 2 at 22:46
• @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.
– D.W.
Mar 3 at 0:35
• 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?
– plop
Mar 3 at 1:18
• 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)$?
– user114966
Mar 3 at 3:03
• @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.
– D.W.
Mar 3 at 5:38