Encontrar un mod de residuo no cuadrático$p$

Question

Permita que$p$ sea un primer grande arbitrario. ¿Hay algún algoritmo rápido para encontrar un mod de residuo no cuadrático$p$? Si$p\equiv 3(\,\mathrm{mod}\, 4)$, entonces$-1\equiv p-1$ siempre es un residuo no cuadrático. Sin embargo, si$p\equiv 1(\,\mathrm{mod}\, 4)$, entonces no podemos simplemente elegir$p-1$. Para$p\equiv 5(\,\mathrm{mod}\, 8)$, también se sabe que$2$ es un residuo no cuadrático, pero tenemos que lidiar con el caso cuando$p\equiv 1(\,\mathrm{mod}\, 8)$. ¿Hay alguna manera más fácil de hacer esto?

Answer 1

Un método, que funciona para todos los impares primos $p$ (no es necesario para comprobar el residuo modulo 4 o módulo 8) es buscar una extraña prime $q$ que $p$ sí es (congruente) un nonquadratic de residuos modulo $p$. A continuación, por la reciprocidad cuadrática que usted elija $q$ o $-q$ de manera tal que la elección ha residuo $1 \bmod 4$, y esta elección es un nonquadratic residuo de mod $p$.

Ejemplo: $p=23$. A continuación,$p=23\equiv 2 \bmod 3$, e $2$ es un nonquadratic de residuos modulo $3$. Desde $-3 \equiv 1 \bmod 4$ podemos deducir que los $-3$ será un nonquadratic de residuos modulo $23$.

Anexo

Cuántas pruebas que debemos esperar antes de golpear en un nomquadratic residuo? Para $q=3$, la mitad de todos los grandes números primos dar un nomquadratic de residuos modulo $3$ (significado $2 \bmod 3$ en lugar de $1 \bmod 3$). Tenemos la misma probabilidad del 50% para cada uno de los prime $q$, para un promedio de dos ensayos generalmente es suficiente. Pero lo que si, metafóricamente, la moneda sigue saliendo colas?

Definir $f(q)$ como sigue:

• $q$ $f(q)$ son ambos impares primos con $f(q)>q$.

• Para cada impar prime $p$ menos de $f(q)$, un nonquadratic residuo se encuentra con un pequeño ensayo prime de $q$, pero $p=f(q)$ requiere pruebas hasta el valor prescrito de $q$.

Por ejemplo, todos los impares primos $3<p<19$ dar un nonquadratic residuos con $q=3$ o $q=5$, pero $p=19$ requiere $q=7$. A continuación,$f(7)=19$. Nos encontramos con que

$f(3)=5$

$f(5)=7$

$f(7)=19$

$f(11)=79$

$f(13)=151$

Se basa en la probabilidad de los argumentos, se espera que el $2^n<f(q)<2^q$ donde $q$ $n$- th impar prime en orden ascendente. Por ejemplo, $q=7$ implica $n=3$, e $f(7)=19$ se encuentra entre $2^3=8$$2^7=128$. Esta es una amplia gama para el valor de $f(q)$, pero si la propuesta de la gama es cierto que garantiza que el máximo número de ensayos requeridos para una gran prime $p$ $O((\log p)^{1+\epsilon})$ arbitrariamente pequeño positivo $\epsilon$. El máximo gotas de a $O(\log p)$ si se trata de una lista de números primos es conocido o (en la actualidad) de manera eficiente genera.