complexity of deciding whether there's a small polynomial with a given root

Question

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?

Answer 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)<i,\|P\|_\infty\le r\}.$$ 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).$$