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.
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\}$.
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
