Algoritmo de Pocklington

El algoritmo de Pocklington es una técnica para resolver una congruencia de la forma

x^{2}\equiv a{\pmod {p}},

donde x y a son números enteros y a es un residuo cuadrático.

El algoritmo es uno de los primeros métodos eficientes para resolver tal congruencia. Fue descrito por H.C. Pocklington en 1917.^[1]

El algoritmo

(Nota: todos los $\equiv$ significan ${\pmod {p}}$ , a menos que se indique lo contrario).

Entradas:

p, un primo impar
a, un número entero que es un residuo cuadrático ${\pmod {p}}$ .

Salidas:

x, un número entero que satisface $x^{2}\equiv a$ . Téngase en cuenta que si x es una solución, −x también es una solución y como p es impar, $x\neq -x$ . Así que siempre hay una segunda solución cuando se encuentra una.

Método de solución

Pocklington separa 3 casos diferentes para p:

El primer caso, si $p=4m+3$ , con $m\in \mathbb {N}$ , la solución es $x\equiv \pm a^{m+1}$ .

El segundo caso, si $p=8m+5$ , con $m\in \mathbb {N}$ y

$a^{2m+1}\equiv 1$ , la solución es $x\equiv \pm a^{m+1}$ .
$a^{2m+1}\equiv -1$ , 2 es un no residuo (cuadrático), por lo que $4^{2m+1}\equiv -1$ . Esto significa que $(4a)^{2m+1}\equiv 1$ entonces $y\equiv \pm (4a)^{m+1}$ es una solución de $y^{2}\equiv 4a$ . Por lo tanto, $x\equiv \pm y/2$ o, si y es impar, $x\equiv \pm (p+y)/2$ .

El tercer caso, si $p=8m+1$ , pon $D\equiv -a$ , por lo que la ecuación a resolver se convierte en $x^{2}+D\equiv 0$ . Ahora se deben encontrar por prueba y error $t_{1}$ y $u_{1}$ de modo que $N=t_{1}^{2}-Du_{1}^{2}$ no sea un residuo cuadrático. Además, entonces

t_{n}={\frac {(t_{1}+u_{1}{\sqrt {D}})^{n}+(t_{1}-u_{1}{\sqrt {D}})^{n}}{2}},\qquad u_{n}={\frac {(t_{1}+u_{1}{\sqrt {D}})^{n}-(t_{1}-u_{1}{\sqrt {D}})^{n}}{2{\sqrt {D}}}}

.

Ahora se cumplen las siguientes igualdades:

t_{m+n}=t_{m}t_{n}+Du_{m}u_{n},\quad u_{m+n}=t_{m}u_{n}+t_{n}u_{m}\quad {\mbox{and}}\quad t_{n}^{2}-Du_{n}^{2}=N^{n}

.

Suponiendo que p es de la forma $4m+1$ (lo cual es verdadero si p es de la forma $8m+1$ ), D es un residuo cuadrático y $t_{p}\equiv t_{1}^{p}\equiv t_{1},\quad u_{p}\equiv u_{1}^{p}D^{(p-1)/2}\equiv u_{1}$ . Ahora las ecuaciones

t_{1}\equiv t_{p-1}t_{1}+Du_{p-1}u_{1}\quad {\mbox{and}}\quad u_{1}\equiv t_{p-1}u_{1}+t_{1}u_{p-1}

dan una solución $t_{p-1}\equiv 1,\quad u_{p-1}\equiv 0$ .

Sea $p-1=2r$ . Luego $0\equiv u_{p-1}\equiv 2t_{r}u_{r}$ . Esto significa que $t_{r}$ o $u_{r}$ son divisibles por p. Si es $u_{r}$ , colóquese $r=2s$ y procédase de manera similar con $0\equiv 2t_{s}u_{s}$ . No todo $u_{i}$ es divisible por p, ya que $u_{1}$ no lo es. El caso $u_{m}\equiv 0$ con m impar es imposible, porque $t_{m}^{2}-Du_{m}^{2}\equiv N^{m}$ se cumple y esto significaría que $t_{m}^{2}$ es congruente con un no residuo cuadrático, lo cual es una contradicción. Así que este ciclo se detiene cuando $t_{l}\equiv 0$ para un valor l en particular. Esto da $-Du_{l}^{2}\equiv N^{l}$ , y como $-D$ es un residuo cuadrático, l debe ser par. Hágase $l=2k$ , luego $0\equiv t_{l}\equiv t_{k}^{2}+Du_{k}^{2}$ . Entonces la solución de $x^{2}+D\equiv 0$ se obtiene resolviendo la congruencia lineal $u_{k}x\equiv \pm t_{k}$ .

Ejemplos

Los siguientes son cuatro ejemplos, correspondientes a los 3 casos diferentes en los que Pocklington dividió las formas de p. Todos los $\equiv$ se toman como módulos en el ejemplo.

Ejemplo 0

x^{2}\equiv 43{\pmod {47}}.

Este es el primer caso, según el algoritmo, $x\equiv 43^{(47+1)/2}=43^{12}\equiv 2$ , pero entonces $x^{2}=2^{2}=4$ y no 43, por lo que no se debería aplicar el algoritmo en absoluto. La razón por la que el algoritmo no es aplicable es que a=43 es un no residuo cuadrático para p=47.

Ejemplo 1

Resuelve la congruencia

x^{2}\equiv 18{\pmod {23}}.

El módulo es 23. Esto es $23=4\cdot 5+3$ , entonces $m=5$ . La solución debería ser $x\equiv \pm 18^{6}\equiv \pm 8{\pmod {23}}$ , lo cual es cierto: $(\pm 8)^{2}\equiv 64\equiv 18{\pmod {23}}$ .

Ejemplo 2

Resuelve la congruencia

x^{2}\equiv 10{\pmod {13}}.

El módulo es 13. Esto es $13=8\cdot 1+5$ , entonces $m=1$ . Ahora verificando $10^{2m+1}\equiv 10^{3}\equiv -1{\pmod {13}}$ . Entonces la solución es $x\equiv \pm y/2\equiv \pm (4a)^{2}/2\equiv \pm 800\equiv \pm 7{\pmod {13}}$ . Esto es cierto: $(\pm 7)^{2}\equiv 49\equiv 10{\pmod {13}}$ .

Ejemplo 3

Resuelve la congruencia $x^{2}\equiv 13{\pmod {17}}$ . En este caso, escríbase $x^{2}-13=0$ . Primero se debe encontrar $t_{1}$ y que $u_{1}$ tales que $t_{1}^{2}+13u_{1}^{2}$ sea un residuo cuadrático. Tómese por ejemplo $t_{1}=3,u_{1}=1$ . Ahora se debe encontrar $t_{8}$ , $u_{8}$ calculando

t_{2}=t_{1}t_{1}+13u_{1}u_{1}=9-13=-4\equiv 13{\pmod {17}},

u_{2}=t_{1}u_{1}+t_{1}u_{1}=3+3\equiv 6{\pmod {17}}.

Y de manera similar $t_{4}=-299\equiv 7{\pmod {17}},u_{4}=156\equiv 3{\pmod {17}}$ tal que $t_{8}=-68\equiv 0{\pmod {17}},u_{8}=42\equiv 8{\pmod {17}}.$

Dado que $t_{8}=0$ , se obtiene la ecuación $0\equiv t_{4}^{2}+13u_{4}^{2}\equiv 7^{2}-13\cdot 3^{2}{\pmod {17}}$ que lleva a resolver la ecuación $3x\equiv \pm 7{\pmod {17}}$ . Esta igualdad tiene la solución $x\equiv \pm 8{\pmod {17}}$ . De hecho, $(\pm 8)^{2}=64\equiv 13{\pmod {17}}$ .