Solve $x^2\equiv 1001 \pmod{3011}$

Question

I am looking for the method and answer for solving congruences like this one:

$x^2 ≡ 1001\pmod {3011}$

Answer 1

$1001=7\cdot 11\cdot 13$ and $3011$ is prime. By Quadratic Reciprocity $7\cdot 11\cdot 13$ is a quadratic residue, because

$$\left(\frac{7}{3011}\right)=-\left(\frac{3011}{7}\right)=-\left(\frac{1}{7}\right)=-1$$

$$\left(\frac{11}{3011}\right)=-\left(\frac{3011}{11}\right)=-\left(\frac{8}{11}\right)=1$$

$$\left(\frac{13}{3011}\right)=\left(\frac{3011}{13}\right)=\left(\frac{8}{13}\right)=-1$$

So by Euler's Criterion $1001^{1505}\equiv 1\pmod{3011}$, so $1001^{1506}\equiv 1001\equiv x^2\pmod{3011}$, so $x\equiv \pm1001^{753}\pmod{3011}$ are all the solutions to $x^2\equiv 1001\pmod{3011}$.

The answer is $x\equiv \pm 745\pmod{3011}$, but it'll require quite heavy calculations. You can use this method (repeated squaring):

$$1001^2\equiv 2349,\, 1001^4\equiv 2349^2\equiv 1649,\, 1001^8\equiv 1649^2\equiv 268\pmod{3011} $$

$$1001^{16}\equiv 268^2\equiv 2571,\, 1001^{32}\equiv 2571^2\equiv 896\pmod{3011}$$

$$1001^{64}\equiv 896^2\equiv 1890,\, 1001^{128}\equiv 1890^2\equiv 1054\pmod{3011}$$

$$1001^{256}\equiv 1054^2\equiv 2868,\, 1001^{512}\equiv 2868^2\equiv 2383\pmod{3011}$$

$753=1011110001_2$, so $$1001^{753}\equiv 1001^{512}1001^{128}1001^{64}1001^{32}1001^{16}1001\pmod{3011}$$

$$\equiv 2383\cdot 1054\cdot 1890\cdot 896\cdot 2571\cdot 1001\equiv 745\pmod{3011}$$