El primer$4$ primes$p$ para el cual$15347$ tiene una modificación de raíz cuadrada$p$ son$2, 17, 23,$ y$29$

Question

Estoy leyendo sobre el artículo de Quadratic Sieve en wiki y no entiendo la parte del tamiz.

El artículo dice:

El primer$4$ primes$p$ para el cual$15347$ tiene una modificación de raíz cuadrada$p$ son$2, 17, 23,$ y$29$

¿Cómo se calculó$2,17,23,$ y$29$? Si puedes, explícame la idea y el cálculo exacto.

Answer 1

Podría usar la reciprocidad cuadrática, como se sugiere en los comentarios, pero esos números primos son tan pequeños que un enfoque de fuerza bruta también es razonable. Para saber si un$n$ grande tiene una raíz cuadrada modulo un% primo pequeño $p$, primero calcule$x = n \bmod p$, y luego verifique si$y^2 \equiv x \bmod p$ para algún$y \in \{0,1,\ldots,(p-1)/2\}$.