Let $f(x)\in\mathbb{Z}[x]$, let $N$ be an integer with known factorization into prime elements. I want to know why it is easy to solve efficiently the equation $f(x)=0\ mod\ N$.???
3
-
$\begingroup$ In general $N \gt 1$ an integer will be a product of prime powers $p^k$. The procedure you presumably want explained is how to piece together the solutions of $f(x) \equiv 0 \bmod p^k$ into solutions of $f(x) \equiv 0 \bmod N$. This is generally easy, but it leaves the possibly difficult task of solving for solutions modulo certain prime powers. $\endgroup$– hardmathCommented Jan 17 at 20:59
-
1$\begingroup$ @hardmath solving polynomial equations modulo prime powers is easy. The general technique is known as Hensel Lifting, and is a generalization of root-finding methods over $\mathbb{R}$ (Newton-Raphsom iteration) to modular integers. $\endgroup$– Mark Schultz-Wu ♦Commented Jan 17 at 21:52
-
1$\begingroup$ @Mark I'm familiar with Hensel lifting. It requires solving the base case, the polynomial modulo a prime. Sometimes a root exists, and sometimes it doesn't. In any case the OP should clarify if they have the entire solution process in mind or just the piecing together of solutions (modulo prime powers). $\endgroup$– hardmathCommented Jan 17 at 21:59
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
The Chinese Remainder Theorem gives an isomorphism
$$\mathbb{Z}[x]/N\cong \prod_i \mathbb{Z}[x]/p_i^{e_i}$$
where $N = \prod_i p_i^{e_i}$ is the prime factorization. Both directions of this isomorphism are explicit, but the map $\mapsto$ is simply
$$f(x)\bmod N\mapsto (f(x)\bmod p_1^{e_1},\dots, f(x)\bmod p_k^{e_i})$$
This is to say that $f(x)\bmod N = 0$ if and only if $\forall_i f(x)\bmod p_i^{e_i} = 0$. So to find solutions to $f(x)\bmod N = 0$, it suffices to
- Find solutions to $f(X)\bmod p_i^{e_i}$ for each $i$, and then
- Take their intersection.
Finding solutions to $f(x) \equiv 0\bmod p_i$ is easy. This is a polynomial equation in $\mathbb{Z}/p_i\mathbb{Z}[x]$, e.g. over a finite field. These are easy to solve, as you can just compute $\mathsf{gcd}(f(x), x^{p_i}-x$) using the Euclidean algorithm. You then need to extend these solutions to solutions $\bmod p_i^{e_i}$. As mentioned in the comments, this can be done using Hensel Lifting. Do this for each $i$, then find the intersection, and you are done.
