# polynomial modulo for higher degree

Given $f(x) , n, g(x)$ where $g(x)$ is usually of a small degree then if we find $h_1(x)$ such that $f(x)\equiv h_1(x)\mod \{n,g(x)\}$ ,

Is there any algorithm to find $h_2(x)$ such that $f(x)\equiv h_2(x)\mod \{n,(g(x))^r\}$ where given value of $r>1,n>2$ and $f(x),g(x),h_1(x),h_2(x)$ are all polynomials.

Also I would like to know, where can I get best knowledge on polynomial modulo where I can find basic algorithms to solve problems such as above. I mean can anyone suggest me good books.

• What do you mean by $f\equiv h_2 \mod {n,g }$? I have never seen a double argument for $\mod{u,v}$. – Elaqqad Jul 4 '15 at 11:46
• $n$ is Integer and $g(x)$ is polynomial – smslce Jul 4 '15 at 11:47
• that notation of double arguments , I pick it from mathematica wolfram – smslce Jul 4 '15 at 11:49
• I know that for example, if we write $a\equiv b \mod n$ then this means that there exist $k$ such that $a=b+kn$ but if we write $a\equiv b \mod u,v$ then what does it mean?,I'm sorry I can't help here if I did not find what does it mean – Elaqqad Jul 4 '15 at 11:49
• In my answer I used the second one $\mathbb{Z}[x]/<n,g(x)>$ or $\mathbb{Z}/(n)[X]$ – Elaqqad Jul 4 '15 at 12:20

First of all , here is the meaning of the notation (a mathematician (even a student) never uses a notation which does not understand) : $$f \equiv h \mod \{n,g\} \iff f(x)-h(x)\equiv q(x). g(x) \mod n$$ This notation can be seen also as the definition of congruence in the ring $F_n[X]$. So we will her eliminate $n$ and say only that : Let $f,g,h_1\in F_n[X]$ such that : $$f(x)=h_1(x) \mod g(x)$$ (which means exactly the same thing as your first condition) can we deduce anything about : $$f(x)\equiv h_2(x) \mod g(x)^r$$
the first thing you have to know is that $h_2$ contain a lot of information compared to $h_1$ because $g^r$ has a large degree than $g$ which means that even if we have $h_1$ we have to do a large number of operations in order to obtain $h_2$, in the following lines I will describe a method to obtain $h_2$.
In order to use $h_1$ we can write: $$h_2(x)=a_0(x)+a_1(x)g(x)+\cdots+a_{r-1}(x)g(x)^{r-1}$$
with $a_0(x)=h_1(x)$ and you can compute $a_1(x)$ as: $$f_1(x)=\frac{f(x)-a_0(x)}{g(x)}\equiv a_1(x) \mod g(x)$$
and you can continue : $$f_2(x)=\frac{f_1(x)-a_1(x)}{g(x)}\equiv a_2(x) \mod g(x)$$ $$f_3(x)=\frac{f_2(x)-a_2(x)}{g(x)}\equiv a_3(x) \mod g(x)$$ and so on ( repeat $r$ times)
This is "an algorithm" but I don't know if it's the minimal one,The only thing I can tell and that you have to understand is the fact that even if you have given $h_1(x)$ you have to do a lot of calculus in order to compute $h_2(x)$