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?

  • $\begingroup$ @EmilJeřábek that's very helpful. thank you $\endgroup$ Jun 27, 2019 at 16:33
  • $\begingroup$ @Emil, that looks to me like it should be an answer. $\endgroup$ Jun 28, 2019 at 22:40
  • 1
    $\begingroup$ I converted the comments to a proper answer. $\endgroup$ Jul 1, 2019 at 12:38

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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