Raíces cuadradas iteradas sobre campo finito. ¿Cuándo nos topamos con un no residente?

Question

Supongamos que estamos trabajando dentro de los enteros modulo $p$ donde $p$ es de alguna extraña primer número. Supongamos que $x_0$ es un (distinto de cero) de residuos cuadráticos mod $p$, entonces existe una $x_1$ tal que $x_1^2 \equiv x_0 \pmod{p}$. Deje $x_1$ ser una raíz de $x_0$. Ahora, si $x_1$ es también una ecuación cuadrática de residuos de mod $p$ entonces podemos permitir $x_2$ ser tal que $x_2^{2} \equiv x_1 \pmod{p}$. Supongamos que repetimos esta operación $n$ veces lo hemos $x_n^2 \equiv x_{n-1} \pmod{p}$ o, si prefieres $x_n^{2^n} \equiv x_0 \pmod{p}$.

Es de todos modos hay que determinar, sin calcular todas las raíces en el campo, si, por continuar con este proceso de toma de raíces cuadradas, se ejecutará en algunos $m$ tal que $x_m$ no es un residuo cuadrático de mod $p$? Por el contrario, existe alguna $l$ que si $x_l$ también es un residuo cuadrático entonces podemos concluir que no $m$ existe? En ambos casos, podemos obtener cualquier tipo de límites en las $m$ e $l$ mejor que 'menos que (p-1)/2'?

Gracias por su tiempo y consideración. Espero que estés teniendo un día maravilloso.

Answer 1

Supongo que $p$ es impar y que vamos a empezar con un valor distinto de cero residuos cuadráticos $x$.

La proposición:

• Si $p\equiv3\pmod{4}$, la iteración se puede ejecutar sin cesar, o ser terminado en cualquier paso, dependiendo de la squareroot es elegido.
• Si $p\equiv1\pmod{4}$ y la orden de $m$ de la partida cuadrado es par, a continuación, el squareroot iteración termina exactamente después de $t$ pasos, independientemente de intermedio signo de decisiones, con $t$ siendo el entero positivo tal que $2^t$ divide $\frac{p-1}{m}$ con impar cofactor.
• Si $p\equiv1\pmod{4}$, y el fin de la partida la plaza es impar, a continuación, el squareroot iteración se puede ejecutar sin cesar, o en cualquier etapa del led para el determinismo de la final en la forma de una orden de la plaza, dependiendo de la squareroot es elegido.

Comentario: Para el tratamiento aquí, impar de factores en el orden de $m$ de % de $x$ son irrelevantes. Así que uno podría escribir $p-1=2^r u$ con $u$ impar, a continuación, establezca $m$ a la orden de $x^u$ que ahora debe tener la forma $2^j$ con entero no negativo $j<r$, la igualdad excluidos debido a $x$ es un cuadrado. Por lo tanto $m$ es impar si y sólo si $j=0$, es decir, $x^u\equiv1\pmod{p}$. De lo contrario, $m$ es incluso y $t=r-j$.

Prueba:

Si $\left(\frac{-1}{p}\right)=-1$, es decir, $p\equiv3\pmod{4}$, a continuación, exactamente una de las raíces es una ecuación cuadrática de residuos.

A la hora de levantar residuos cuadráticos para algunos el poder, los exponentes son equivalentes modulo $m=\frac{p-1}{2}$. Para $p\equiv3\pmod{4}$ nos encontramos con $m$ es impar, entonces existe un número entero exponente $h\equiv2^{-1}\pmod{m}$, es decir,$h=\frac{p+1}{4}$, y crianza de los residuos cuadráticos $x$ a de la $h$-ésima potencia del modulo $p$ le da a uno squareroot de $x$. Ahora desde $h$ es una potencia de $x$, e $x$ es un residuo cuadrático módulo $p$, entonces también lo es $h$. En otras palabras, la exponenciación basado en la forma de squareroot encontrar siempre los rendimientos de una raíz que es una ecuación cuadrática de residuos.

En consecuencia, Para $p\equiv3\pmod{4}$, el proceso de iteración squareroots basado en la toma de $h$-th poderes nunca se ejecuta en una ecuación cuadrática nonresidue. Por otro lado, si la reserva de las decisiones en cuanto a cual de los dos las posibles raíces de su uso, puede elegir el nonresidue $-x^h$ en lugar de $x^h$ después de cualquier paso que te gusta, y así terminar la iteración cuando quieras.

Esto deja el caso de $\left(\frac{-1}{p}\right)=+1$, es decir, $p\equiv1\pmod{4}$, para su consideración. En ese caso, ninguno o ambos raíces de $x\pmod{p}$ son residuos cuadráticos.

Supongamos que el orden de $m$ de % de $x$ en $(\mathbb{Z}/p\mathbb{Z})^\times$ es incluso. Dado que el $x$ es una ecuación cuadrática de los residuos y $(-1)^{(p-1)/m} \equiv \left(x^{m/2}\right)^{(p-1)/m} \equiv x^{(p-1)/2} \equiv +1\pmod{p}$ nos encontramos con que $\frac{p-1}{m}$ es incluso.

Deje $t$ el valor del entero positivo tal que $2^t$ divide $\frac{p-1}{m}$ con impar cofactor. Desde $m$ es aún, sabemos que $2^t$ divide $\frac{p-1}{2}$.

Tengo que usar logaritmos discretos ahora. Deje $g$ ser un generador de $(\mathbb{Z}/p\mathbb{Z})^\times$ y $k$ el menor entero no negativo tal que $g^k=x$. Desde $m$ es el menor entero positivo tal que $p-1$ divide $km$, sabemos que $2^t$ divide $k$. También sabemos que $2(p-1)$ no divide $km$, porque de lo contrario $m$ puede ser reducido a la mitad el cual estaría en contradicción con su minimality. Esto significa que $2^{t+1}$ no divide $k$, por lo $2^t$ es el máximo poder de $2$ dividiendo $k$. Tenga en cuenta que $t$ ha sido definida independientemente de $g$. Llegamos a la conclusión de que al menos $t+1$ dígitos binarios de $k$, de mayor peso a menor, son exactamente $(1,0,\ldots,0)$, independientemente de $g$.

Los dos squareroots de $x$ puede ser expresado como $g^{k/2}$ e $g^{(k+p-1)/2}$. En consecuencia, el discreto logaritmos de las raíces son $\frac{k}{2}$ e $\frac{k+p-1}{2}$. Tenga en cuenta que ambos registros son congruentes modulo $\frac{p-1}{2}$ y así congruentes módulo del divisor $2^t$, por lo tanto, squareroot registros de acuerdo en sus últimos $t$ bits que son exactamente $(1,0,\ldots,0)$. En consecuencia, el orden de cada squareroot será el doble que la de $x$, por lo tanto, incluso, para la iteración no se ejecutará en otros subcases.

Cada squareroot iteración paso reduce el $t$ por uno, esencialmente cortando el de más a la derecha bit cero en el conocido $t$-patrón de bits de los discretos registros. El squareroot iteración termina cuando el menos significativo bit se convierte en conjunto, y sabemos que esto sucede después de exactamente $t$ squareroot pasos.

Finalmente, supongamos que el orden de $m$ de % de $x$ en $(\mathbb{Z}/p\mathbb{Z})^\times$ es impar. A continuación, el squareroots de $x$ se $\pm x^h$ donde $h=\frac{m+1}{2}$, y como el poder de los residuos cuadráticos $x$, multiplicado con un residuo cuadrático $\pm1$, esas raíces son residuos cuadráticos demasiado.

Ahora $2h-m=1$ implica que el $h$ es coprime a $m$, por lo tanto el orden de la squareroot $+x^h$ permanece en $m$. En consecuencia, la elección de $+x^h$ como el squareroot para una nueva iteración nos llevaría de nuevo a este extraño caso de la orden. Siempre la elección de $+x^h$, por lo tanto nunca se ejecuta en una ecuación cuadrática nonresidue.

Teniendo en cuenta que el orden de $-1$ es $2$ y $m$ es impar, nos encontramos con el orden de la squareroot $-x^h$ a $2m$. En consecuencia, la elección de $-x^h$ como el squareroot para una nueva iteración nos llevaría a la orden en caso de que conduce a un determinista final.

Answer 2

Usted tiene un campo finito de orden $p$, y es multiplicativo grupo cíclico de orden $p-1$. Así que hay un generador de $\alpha$ para este grupo multiplicativo, y cualquier elemento de $\mathbb{F}_{p}^{*}$ puede ser escrito como $\alpha^{k}$. Es una ecuación cuadrática de residuos iff $k$ es incluso, en cuyo caso las raíces cuadradas se $\pm \alpha^{k/2}$ (que a su vez puede ser escrito como una potencia de $\alpha$).

No creo que usted puede incluso alcanzar la $(p-1)/2$ como límite en m. Por ejemplo, considere el $\mathbb{F}_{7}$.Observe que $2^{2} = 4$ e $4^{2} = 2$, así que usted puede continuar indefinidamente.

Answer 3

Si $x$ tiene orden impar (es decir, $g$), a continuación, $y = x^{(g+1)/2}$ es una raíz cuadrada de $x$. También, $y$ tiene orden impar, por lo que puede repetir.

Si usted llevó a $y = -x^{(g+1)/2}$ en lugar de eso, usted podría, eventualmente, llegar a un nonresidue.

También, recordar que estamos trabajando en un campo finito hace que el problema demasiado difícil; en teoría, todo lo que usted está preguntando acerca de es el comportamiento de la división por $2$ en un grupo cíclico. De hecho, incluso se puede descomponer el grupo cíclico como un producto de $C_{2^k} \times C_m$ donde $m$ es extraño... y puede omitir $C_m$ completamente ya que nada interesante sucede allí: siempre se puede dividir por $2$ modulo $m$.