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

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.H.C. Pocklington, Proceedings of the Cambridge Philosophical Society, Volume 19, pages 57–58

El algoritmo (Nota: todos los significan , a menos que se indique lo contrario).

Entradas: p, un primo impar a, un número entero que es un residuo cuadrático .

Salidas: x, un número entero que satisface . Téngase en cuenta que si x es una solución, −x también es una solución y como p es impar, . 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 , con , la solución es .

El segundo caso, si , con y , la solución es . , 2 es un no residuo (cuadrático), por lo que . Esto significa que entonces es una solución de . Por lo tanto, o, si y es impar, .

El tercer caso, si , pon , por lo que la ecuación a resolver se convierte en . Ahora se deben encontrar por prueba y error y de modo que no sea un residuo cuadrático. Además, entonces . Ahora se cumplen las siguientes igualdades: . Suponiendo que p es de la forma (lo cual es verdadero si p es de la forma ), D es un residuo cuadrático y . Ahora las ecuaciones

dan una solución .

Sea . Luego . Esto significa que o son divisibles por p. Si es , colóquese y procédase de manera similar con . No todo es divisible por p, ya que no lo es. El caso con m impar es imposible, porque se cumple y esto significaría que es congruente con un no residuo cuadrático, lo cual es una contradicción. Así que este ciclo se detiene cuando para un valor l en particular. Esto da , y como es un residuo cuadrático, l debe ser par. Hágase , luego . Entonces la solución de se obtiene resolviendo la congruencia lineal .

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

Ejemplo 0

Este es el primer caso, según el algoritmo, , pero entonces 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

El módulo es 23. Esto es , entonces . La solución debería ser , lo cual es cierto: .

Ejemplo 2 Resuelve la congruencia

El módulo es 13. Esto es , entonces . Ahora verificando . Entonces la solución es . Esto es cierto: .

Ejemplo 3 Resuelve la congruencia . En este caso, escríbase . Primero se debe encontrar y que tales que sea un residuo cuadrático. Tómese por ejemplo . Ahora se debe encontrar , calculando

Y de manera similar tal que

Dado que , se obtiene la ecuación que lleva a resolver la ecuación . Esta igualdad tiene la solución . De hecho, .

Referencias

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

Categoría:Aritmética modular