Algoritmo de Pocklington

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

x 2 ≡ a ( mod p ) , {\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

[editar]

(Nota: todos los  ≡ {\displaystyle \equiv } significan  ( mod p ) {\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  ( mod p ) {\displaystyle {\pmod {p}}} .

Salidas:

* x, un número entero que satisface  x 2 ≡ a {\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,  x ≠ − x {\displaystyle x\neq -x} . Así que siempre hay una segunda solución cuando se encuentra una.

### Método de solución

[editar]

Pocklington separa 3 casos diferentes para p:

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

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

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

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

t n = ( t 1 + u 1 D ) n + ( t 1 − u 1 D ) n 2 , u n = ( t 1 + u 1 D ) n − ( t 1 − u 1 D ) n 2 D {\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:

t m + n = t m t n + D u m u n , u m + n = t m u n + t n u m and t n 2 − D u n 2 = N n {\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  4 m + 1 {\displaystyle 4m+1} (lo cual es verdadero si p es de la forma  8 m + 1 {\displaystyle 8m+1} ), D es un residuo cuadrático y  t p ≡ t 1 p ≡ t 1 , u p ≡ u 1 p D ( p − 1 ) / 2 ≡ u 1 {\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

t 1 ≡ t p − 1 t 1 + D u p − 1 u 1 and u 1 ≡ t p − 1 u 1 + t 1 u p − 1 {\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  t p − 1 ≡ 1 , u p − 1 ≡ 0 {\displaystyle t_{p-1}\equiv 1,\quad u_{p-1}\equiv 0} .

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

## Ejemplos

[editar]

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

[editar]

x 2 ≡ 43 ( mod 47 ) . {\displaystyle x^{2}\equiv 43{\pmod {47}}.}

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

[editar]

Resuelve la congruencia

x 2 ≡ 18 ( mod 23 ) . {\displaystyle x^{2}\equiv 18{\pmod {23}}.}

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

### Ejemplo 2

[editar]

Resuelve la congruencia

x 2 ≡ 10 ( mod 13 ) . {\displaystyle x^{2}\equiv 10{\pmod {13}}.}

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

### Ejemplo 3

[editar]

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

t 2 = t 1 t 1 + 13 u 1 u 1 = 9 − 13 = − 4 ≡ 13 ( mod 17 ) , {\displaystyle 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 ≡ 6 ( mod 17 ) . {\displaystyle u_{2}=t_{1}u_{1}+t_{1}u_{1}=3+3\equiv 6{\pmod {17}}.}

Y de manera similar  t 4 = − 299 ≡ 7 ( mod 17 ) , u 4 = 156 ≡ 3 ( mod 17 ) {\displaystyle t_{4}=-299\equiv 7{\pmod {17}},u_{4}=156\equiv 3{\pmod {17}}} tal que  t 8 = − 68 ≡ 0 ( mod 17 ) , u 8 = 42 ≡ 8 ( mod 17 ) . {\displaystyle t_{8}=-68\equiv 0{\pmod {17}},u_{8}=42\equiv 8{\pmod {17}}.}

Dado que  t 8 = 0 {\displaystyle t_{8}=0} , se obtiene la ecuación  0 ≡ t 4 2 + 13 u 4 2 ≡ 7 2 − 13 ⋅ 3 2 ( mod 17 ) {\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  3 x ≡ ± 7 ( mod 17 ) {\displaystyle 3x\equiv \pm 7{\pmod {17}}} . Esta igualdad tiene la solución  x ≡ ± 8 ( mod 17 ) {\displaystyle x\equiv \pm 8{\pmod {17}}} . De hecho,  ( ± 8 ) 2 = 64 ≡ 13 ( mod 17 ) {\displaystyle (\pm 8)^{2}=64\equiv 13{\pmod {17}}} .

## Referencias

[editar]

1. ↑ H.C. Pocklington, Proceedings of the Cambridge Philosophical Society, Volume 19, pages 57–58

## Bibliografía

[editar]

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

Control de autoridades|

* Proyectos Wikimedia
* Datos: Q17099582

|

* Datos: Q17099582