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.
, a menos que se indique lo contrario).
Entradas: Salidas: Pocklington separa 3 casos diferentes para p: El primer caso, si
y El tercer caso, si
, por lo que la ecuación a resolver se convierte en
Ahora se deben encontrar por prueba y error
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
Esto significa que
y procédase de manera similar con
es divisible por p, ya que
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
es un residuo cuadrático, l debe ser par.
se obtiene resolviendo la congruencia lineal
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.
Este es el primer caso, según el algoritmo,
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.
Primero se debe encontrar
Ahora se debe encontrar
calculando Y de manera similar
que lleva a resolver la ecuación