Algoritmo de Pocklington

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

${\displaystyle 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 ${\displaystyle \equiv }$ significan ${\displaystyle {\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 ${\displaystyle {\pmod {p}}}$.

Salidas:

• x, un número entero que satisface ${\displaystyle 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, ${\displaystyle 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 ${\displaystyle p=4m+3}$, con ${\displaystyle m\in \mathbb {N} }$, la solución es ${\displaystyle x\equiv \pm a^{m+1}}$.

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

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

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

${\displaystyle 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:

${\displaystyle 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 ${\displaystyle 4m+1}$ (lo cual es verdadero si p es de la forma ${\displaystyle 8m+1}$), D es un residuo cuadrático y ${\displaystyle 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

${\displaystyle 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 ${\displaystyle t_{p-1}\equiv 1,\quad u_{p-1}\equiv 0}$.

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

Ejemplo 0

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

Este es el primer caso, según el algoritmo, ${\displaystyle x\equiv 43^{(47+1)/2}=43^{12}\equiv 2}$, pero entonces ${\displaystyle 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

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

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

Ejemplo 2

Resuelve la congruencia

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

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

Ejemplo 3

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

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

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

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

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

Referencias

Bibliografía

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