Algoritmo de Pocklington

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

$x^2\equiv a(\mathrm{mod}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 $(\mathrm{mod}p)$, a menos que se indique lo contrario).

Entradas:

• p, un primo impar
• a, un número entero que es un residuo cuadrático $(\mathrm{mod}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\ne -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-D{u}_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},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+D{u}_m{u}_n,u_{m+n}=t_m{u}_n+t_n{u}_m\text{and}{t}_n^2-D{u}_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,u_p\equiv u_1^p{D}^{(p-1)/2}\equiv u_1$. Ahora las ecuaciones

$t_1\equiv t_{p-1}{t}_1+D{u}_{p-1}{u}_1\text{and}{u}_1\equiv t_{p-1}{u}_1+t_1{u}_{p-1}$

dan una solución $t_{p-1}\equiv 1,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-D{u}_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 $-D{u}_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+D{u}_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(\mathrm{mod}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(\mathrm{mod}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(\mathrm{mod}23)$, lo cual es cierto: $(\pm 8{)}^2\equiv 64\equiv 18(\mathrm{mod}23)$.

Ejemplo 2

Resuelve la congruencia

$x^2\equiv 10(\mathrm{mod}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(\mathrm{mod}13)$. Entonces la solución es $x\equiv \pm y/2\equiv \pm (4a{)}^2/2\equiv \pm 800\equiv \pm 7(\mathrm{mod}13)$. Esto es cierto: $(\pm 7{)}^2\equiv 49\equiv 10(\mathrm{mod}13)$.

Ejemplo 3

Resuelve la congruencia $x^2\equiv 13(\mathrm{mod}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(\mathrm{mod}17),$

$u_2=t_1{u}_1+t_1{u}_1=3+3\equiv 6(\mathrm{mod}17).$

Y de manera similar $t_4=-299\equiv 7(\mathrm{mod}17),u_4=156\equiv 3(\mathrm{mod}17)$ tal que $t_8=-68\equiv 0(\mathrm{mod}17),u_8=42\equiv 8(\mathrm{mod}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(\mathrm{mod}17)$ que lleva a resolver la ecuación $3x\equiv \pm 7(\mathrm{mod}17)$. Esta igualdad tiene la solución $x\equiv \pm 8(\mathrm{mod}17)$. De hecho, $(\pm 8{)}^2=64\equiv 13(\mathrm{mod}17)$.

Bibliografía

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