3
$\begingroup$

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.

$\endgroup$

1 Answer 1

10
$\begingroup$

I don't think there's much hope for a general algorithm if the polynomials you are considering have degree so large that one can't store all the coefficients in memory. Then one can't present the polynomial by giving its coefficients, but has to do it some other way, and the right algorithm might depend a lot on how the polynomial is presented.

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

$\endgroup$
4
  • 1
    $\begingroup$ I can choose the prime p of my choice such that $p>2^{2000}$ $\endgroup$
    – Dattier
    Apr 16, 2022 at 13:00
  • $\begingroup$ @Dattier Could you explain more the motivation for this question? $\endgroup$
    – Will Sawin
    Apr 16, 2022 at 13:05
  • $\begingroup$ Randomly solve NP problems $\endgroup$
    – Dattier
    Apr 16, 2022 at 13:10
  • 6
    $\begingroup$ @Dattier I don't think there are good prospects for that. $\endgroup$
    – Will Sawin
    Apr 16, 2022 at 14:22

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.