# Root of polynomials in a finite field

I am looking for a way to find out if a polynomial $$P\in \mathbb Z/p\mathbb Z=\mathbb F_p$$, of great degree, has roots in $$\mathbb F_p$$, with $$p$$ a big prime number.

For example : $$p=2^{2020}-69$$ prime number, $$Q(x)=x^{(p-1)/2} \in \mathbb F_p$$

$$R(x)=2020-\sum\limits_{i=1}^{2020} Q(x+i) \in \mathbb F_p[x]$$.

We want to know if this polynomial $$R$$ have a root on $$\mathbb F_p$$ ?

Is there an algorithm to answer this kind of question in less than an hour?

Edit : Motivation

$$P_i(x)=\dfrac 12 (Q(x+r_i)+1), r_i \in\mathbb F_p$$ $$i=1...2000$$

$$H=P_1\times (1-P_2)\times P_3+P_4\times P_5+....$$

if exists $$a\in \mathbb F_p$$ with $$H(a)=0$$ then the problem sat

$$x_1 \times (1+x_2)\times x_3$$,

$$x_4 \times x_5,....$$ have a solution.

For reference, for a general polynomial of degree that may be large but not quite that large, I believe the usual algorithm is to compute the gcd of your polynomial with $$x^p-x$$, using Euclid's algorithm, noting that for the first step, of finding $$x^p-x$$ modulo $$P$$, it suffices to calculate $$x^p \mod P$$, which can be done rapidly by the exponentiation-by-squaring method.
In your case, the polynomial $$R$$ has some extra structure - its roots arise from chains of $$2020$$ consecutive quadratic residues. This algorithm seems less feasible than the direct algorithm of computing whether $$x$$ is a quadratic residue for each $$x$$ from $$1$$ to $$p$$ and halting if a chain is found, which "merely" takes $$2^{2020}$$ time and not $$2^{2020}$$ space.
I am skeptical that an algorithm much better than the direct one is available, but can't give a rigorous argument for this. (If the $$2020$$ appearing in the sum were smaller, one could express the number of solutions in terms of point counts on hyperelliptic curves of the form $$y^2 = \prod_{i\in S} x+i$$ for $$S$$ a subset of $$\{1,2020\}$$, and apply Kedlaya-type $$p$$-adic algorithms, but since there are $$2^{2020}$$ relevant hyperellipti curves this is not really any improvement.)
• I can choose the prime p of my choice such that $p>2^{2000}$ Apr 16, 2022 at 13:00