<p>Here is an algorithm that solves the problem in time
<span class="math-container">$$\tilde O\Bigl(\min\Bigl\{(2r+1)^{\frac{d+1}2},p^{\frac12\bigl(1+\frac1{\log(r+1)}\bigr)}\Bigr\}\sqrt r\Bigl)\subseteq\tilde O(p).$$</span>
The tildes hide <span class="math-container">$(\log p)^{O(1)}$</span> factors coming from operations in <span class="math-container">$\mathbb F_p$</span> and from implementation of sets by, say, min-heaps.</p>

<p>First, observe that the answer is always YES if <span class="math-container">$d+1\ge\frac{\log(p+1)}{\log(r+1)}$</span>: there are <span class="math-container">$(r+1)^{d+1}\ge p+1$</span> polynomials <span class="math-container">$P$</span> of degree at most <span class="math-container">$d$</span> with coefficients in <span class="math-container">$\{0,\dots,r\}$</span>, hence by the pigeonhole principle, there exist two such polynomials <span class="math-container">$P_0\ne P_1$</span> such that <span class="math-container">$\overline{P_0}(f)=\overline{P_1}(f)$</span>. Then <span class="math-container">$P=P_0-P_1$</span> satisfies the requirements.</p>

<p>Thus, we may assume without loss of generality
<span class="math-container">$$d+1\le\left\lfloor\frac{\log p}{\log(r+1)}\right\rfloor.$$</span>
Then (assuming <span class="math-container">$r\ge1$</span>) 
<span class="math-container">$$(2r+1)^{\frac{d+1}2}\le p^{\frac{\log(2r+1)}{2\log(r+1)}}\le p^{\frac12\bigl(1+\frac1{\log(r+1)}\bigr)},$$</span>
hence it suffices to find an algorithm working in time
<span class="math-container">$$\tilde O\Bigl((2r+1)^{\frac{d+2}2}\Bigr).$$</span></p>

<p>For any <span class="math-container">$i\le d+1$</span>, let
<span class="math-container">$$V_i=\{\overline P(f):P\in\mathbb Z[x],P\ne0,\deg(P)&lt;i,\|P\|_\infty\le r\}.$$</span>
Using this notation, the problem is equivalent to finding out if <span class="math-container">$0\in V_{d+1}$</span>, and we can compute <span class="math-container">$V_i$</span> using a simple recurrence. The whole algorithm looks like this:</p>

<ol>
<li><p>If <span class="math-container">$r=0$</span>, output NO.</p></li>
<li><p>If <span class="math-container">$d+1\ge\frac{\log(p+1)}{\log(r+1)}$</span>, output YES.</p></li>
<li><p>For each <span class="math-container">$j=\lceil\log(d+2)\rceil,\dots,1$</span>, compute <span class="math-container">$V_{\lfloor(d+1)2^{-j}\rfloor}$</span> and <span class="math-container">$f^{\lfloor(d+1)2^{-j}\rfloor}$</span> by using the recurrences
<span class="math-container">$$\begin{align*}
V_0&amp;=\varnothing,\\
V_{2i}&amp;=V_i\cup\bigl\{a+f^ib:a\in V_i\cup\{0\},b\in V_i\bigr\},\\
V_{2i+1}&amp;=V_{2i}\cup\bigl\{a+f^{2i}b:a\in V_{2i}\cup\{0\},b\in\{\pm1,\dots,\pm r\}\bigr\},
\end{align*}$$</span>
where all the arithmetic operations are modulo <span class="math-container">$p$</span>.</p></li>
<li><p>If <span class="math-container">$d$</span> is even, compute <span class="math-container">$V_{\lceil(d+1)/2\rceil}$</span> from <span class="math-container">$V_{\lfloor(d+1)/2\rfloor}$</span> as above.</p></li>
<li><p>If <span class="math-container">$0\in V_{\lceil(d+1)/2\rceil}$</span>, output YES.</p></li>
<li><p>For each <span class="math-container">$a\in V_{\lceil(d+1)/2\rceil}$</span>, if <span class="math-container">$-af^{\lceil(d+1)/2\rceil}\in V_{\lfloor(d+1)/2\rfloor}$</span>, then output YES.</p></li>
<li><p>Output NO.</p></li>
</ol>

<p>It should be clear from the discussion above that the algorithm is correct. Moreover, we have
<span class="math-container">$$|V_i|\le(2r+1)^i,$$</span>
and since these bounds form a geometric series, it is easy to see that the time needed to compute <span class="math-container">$V_i$</span> using the above recurrences is also
<span class="math-container">$$\tilde O\Bigl((2r+1)^i\Bigr).$$</span>
Thus, the algorithm runs in time
<span class="math-container">$$\tilde O\Bigl((2r+1)^{\lceil(d+1)/2\rceil}\Bigr)\subseteq\tilde O\Bigl((2r+1)^{(d+2)/2}\Bigr).$$</span></p>

CC BY-SA 4.0
2019-07-01T12:36:53.287Z
2019-07-01T13:21:58.853Z
2019-07-01T13:21:58.853Z
Emil Jeřábek
<p>Let <span class="math-container">$f\in (\mathbb{Z}/p\mathbb{Z})^\ast$</span> be a nonzero element of a prime finite field.  For <span class="math-container">$d, r\in \mathbb{N}$</span> consider the problem of deciding whether there is a nonzero polynomial <span class="math-container">$$P(x) = a_0 +a_1x+a_2x^2+...+~a_dx^d \in \mathbb{Z}[x]$$</span> of degree not exceeding <span class="math-container">$d$</span>, and also <span class="math-container">$|a_i|\leq r$</span> for all <span class="math-container">$i$</span>, and also such that <span class="math-container">$\overline{P}(x)\in (\mathbb{Z}/p\mathbb{Z})[x]$</span> has <span class="math-container">$f$</span> as a root.  (So this is a decision problem depending on <span class="math-container">$f, p, d, r $</span>).   Is there anything known about the general time complexity of this problem?</p>

CC BY-SA 4.0
2019-06-27T16:33:44.417Z
@EmilJeřábek that's very helpful. thank you
Mr. Cooperman
CC BY-SA 4.0
2019-06-28T22:40:59.407Z
@Emil, that looks to me like it should be an answer.
Peter Taylor
CC BY-SA 4.0
2019-07-01T12:38:44.550Z
I converted the comments to a proper answer.
Emil Jeřábek
<cc.complexity-theory><finite-fields>
complexity of deciding whether there's a small polynomial with a given root
Mr. Cooperman
# complexity of deciding whether there's a small polynomial with a given root

(Asked by: username_0 on 2019-06-27)

Let $f\in (\mathbb{Z}/p\mathbb{Z})^\ast$ be a nonzero element of a prime finite field. For $d, r\in \mathbb{N}$ consider the problem of deciding whether there is a nonzero polynomial $$P(x) = a\_0 +a\_1x+a\_2x^2+...+~a\_dx^d \in \mathbb{Z}[x]$$ of degree not exceeding $d$, and also $|a\_i|\leq r$ for all $i$, and also such that $\overline{P}(x)\in (\mathbb{Z}/p\mathbb{Z})[x]$ has $f$ as a root. (So this is a decision problem depending on $f, p, d, r $). Is there anything known about the general time complexity of this problem?

**Tags:** cc.complexity-theory, finite-fields
> **Comments:**
> **username_0**: @EmilJeřábek that's very helpful. thank you  
> **username_1**: @Emil, that looks to me like it should be an answer.  
> **username_2**: I converted the comments to a proper answer.  

---

## 1 answers

### Answer by username_2 on 2019-07-01. Score: 1

Here is an algorithm that solves the problem in time
$$\tilde O\Bigl(\min\Bigl\{(2r+1)^{\frac{d+1}2},p^{\frac12\bigl(1+\frac1{\log(r+1)}\bigr)}\Bigr\}\sqrt r\Bigl)\subseteq\tilde O(p).$$
The tildes hide $(\log p)^{O(1)}$ factors coming from operations in $\mathbb F\_p$ and from implementation of sets by, say, min-heaps.

First, observe that the answer is always YES if $d+1\ge\frac{\log(p+1)}{\log(r+1)}$: there are $(r+1)^{d+1}\ge p+1$ polynomials $P$ of degree at most $d$ with coefficients in $\{0,\dots,r\}$, hence by the pigeonhole principle, there exist two such polynomials $P\_0\ne P\_1$ such that $\overline{P\_0}(f)=\overline{P\_1}(f)$. Then $P=P\_0-P\_1$ satisfies the requirements.

Thus, we may assume without loss of generality
$$d+1\le\left\lfloor\frac{\log p}{\log(r+1)}\right\rfloor.$$
Then (assuming $r\ge1$)
$$(2r+1)^{\frac{d+1}2}\le p^{\frac{\log(2r+1)}{2\log(r+1)}}\le p^{\frac12\bigl(1+\frac1{\log(r+1)}\bigr)},$$
hence it suffices to find an algorithm working in time
$$\tilde O\Bigl((2r+1)^{\frac{d+2}2}\Bigr).$$

For any $i\le d+1$, let
$$V\_i=\{\overline P(f):P\in\mathbb Z[x],P\ne0,\deg(P)
Using this notation, the problem is equivalent to finding out if $0\in V\_{d+1}$, and we can compute $V\_i$ using a simple recurrence. The whole algorithm looks like this:

1. If $r=0$, output NO.
2. If $d+1\ge\frac{\log(p+1)}{\log(r+1)}$, output YES.
3. For each $j=\lceil\log(d+2)\rceil,\dots,1$, compute $V\_{\lfloor(d+1)2^{-j}\rfloor}$ and $f^{\lfloor(d+1)2^{-j}\rfloor}$ by using the recurrences
   $$\begin{align\*}
   V\_0&=\varnothing,\\
   V\_{2i}&=V\_i\cup\bigl\{a+f^ib:a\in V\_i\cup\{0\},b\in V\_i\bigr\},\\
   V\_{2i+1}&=V\_{2i}\cup\bigl\{a+f^{2i}b:a\in V\_{2i}\cup\{0\},b\in\{\pm1,\dots,\pm r\}\bigr\},
   \end{align\*}$$
   where all the arithmetic operations are modulo $p$.
4. If $d$ is even, compute $V\_{\lceil(d+1)/2\rceil}$ from $V\_{\lfloor(d+1)/2\rfloor}$ as above.
5. If $0\in V\_{\lceil(d+1)/2\rceil}$, output YES.
6. For each $a\in V\_{\lceil(d+1)/2\rceil}$, if $-af^{\lceil(d+1)/2\rceil}\in V\_{\lfloor(d+1)/2\rfloor}$, then output YES.
7. Output NO.

It should be clear from the discussion above that the algorithm is correct. Moreover, we have
$$|V\_i|\le(2r+1)^i,$$
and since these bounds form a geometric series, it is easy to see that the time needed to compute $V\_i$ using the above recurrences is also
$$\tilde O\Bigl((2r+1)^i\Bigr).$$
Thus, the algorithm runs in time
$$\tilde O\Bigl((2r+1)^{\lceil(d+1)/2\rceil}\Bigr)\subseteq\tilde O\Bigl((2r+1)^{(d+2)/2}\Bigr).$$


---

