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.​

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

1. $a^{2m+1}\equiv 1$, la solución es $x\equiv \pm a^{m+1}$.
2. $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}}$.

Bibliografía

• Leonard Eugene Dickson, "History Of The Theory Of Numbers" vol 1 p 222, Chelsea Publishing 1952

• Datos: Q17099582