Given a sequence $\left(\tfrac{x}{p}\right),\left(\tfrac{x+1}{p}\right),\dots,$ how hard it is to find an $x$ that fits?

63 Views Asked by At

Let $p$ be some 1000-bit prime number.

Given a sequence $1$'s and $-1$'s $$\left(\tfrac{x}{p}\right),\left(\tfrac{x+1}{p}\right),\dots,\left(\tfrac{x+80}{p}\right)$$ how hard it is to find an $x \in \mathbb{Z}_p$ if $p$ is prime?

Here $\left(\tfrac{x}{p}\right)$ denotes Legendre symbol, which can be defined as $\left(\tfrac{x}{p}\right) := x^{(p-1)/2} \bmod p$.