# How good are these probabilistic algorithms for the NP-hard problem gcd of sparse polynomials?

defines sparse polynomial as set $\{(a_i,i)\}$ and $f=\sum a_i x^i$.

On p.5:

Theorem 3.3. The followiug problem is NP-hard: Given a set $\{ p_1(x), p_2(x) \ldots , p_k(x)))\}$ of sparse polynomials with integer coefficients, to determine if they have a nontrivial greatest common divisor (the gcd has degree greater than zero).

At integers the gcd of two coprime polynomials $p_1,p_2$ is bounded by their resultant $res(p_1,p_2)$. For $k$ coprime polynomials $p_i$ the gcd at integers is bounded by the "total resultant" $res(res(res(p_1,p_2),p_3 \ldots p_k$). This means that if $p_i$ are coprime (not necessarily pairwise coprime) the $p_i$ vanish simultaneously modulo finitely many integers $q_i$. If $gcd(p_i)=g$ with $g$ non-constant, then for a root $r$ of $g$ modulo $n$ all $p_i(r)$ vanish modulo $n$.

This gives probabilistic algorithm: choose small prime power $p^k$, for $a \in \mathbb{Z}/p^k \mathbb{Z}$ check if $p_i(a)$ vanish simultaneously. If this happens, it increases the probability of non-constant gcd. Repeat with another prime power $p^k$.

Another possibility is to work modulo $p$ and try to do Hensel lifting of a common root $a$ for each $p_i$, since the derivative of sparse polynomial is efficiently computable. If the gcd is constant, we can't do too much Hensel lifting. If the gcd $g$ is non-constant and we he have found root $a$ of $g$ which is simple root modulo all $p_i$, we can do Hensel lifting forever.

If the total resultant is $1$, the $p_i$ will never vanish modulo $n$.

How good are these probabilistic algorithms? Any other special cases when they are deterministic?

Finding bound for the total resultant of the sparse polynomials in casea it is constant may help.