2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ What do you mean by $f\equiv h_2 \mod {n,g }$? I have never seen a double argument for $\mod{u,v}$. $\endgroup$ – Elaqqad Jul 4 '15 at 11:46
  • $\begingroup$ $n$ is Integer and $g(x)$ is polynomial $\endgroup$ – smslce Jul 4 '15 at 11:47
  • $\begingroup$ that notation of double arguments , I pick it from mathematica wolfram $\endgroup$ – smslce Jul 4 '15 at 11:49
  • $\begingroup$ 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 $\endgroup$ – Elaqqad Jul 4 '15 at 11:49
  • 1
    $\begingroup$ In my answer I used the second one $\mathbb{Z}[x]/<n,g(x)>$ or $\mathbb{Z}/(n)[X]$ $\endgroup$ – Elaqqad Jul 4 '15 at 12:20
2
$\begingroup$

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)$

| cite | improve this answer | |
$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.