El algoritmo de Pocklington

Pocklington distingue 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 tanto${\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 eso${\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}$, poner${\displaystyle D\equiv -a}$, por lo que la ecuación a resolver se convierte en${\displaystyle x^{2}+D\equiv 0}$Ahora, descúbrelo por ensayo y error.${\displaystyle t_{1}}$y${\displaystyle u_{1}}$de modo que${\displaystyle N=t_{1}^{2}-Du_{1}^{2}}$es un no residuo cuadrático. Además, sea

${\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{y}}\quad t_{n}^{2}-Du_{n}^{2}=N^{n}}$.

Suponiendo que p es de la forma${\displaystyle 4m+1}$(lo cual es cierto 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{y}}\quad u_{1}\equiv t_{p-1}u_{1}+t_{1}u_{p-1}}$

Proporcione una solución${\displaystyle t_{p-1}\equiv 1,\quad u_{p-1}\equiv 0}$.

Dejar${\displaystyle p-1=2r}$. Entonces${\displaystyle 0\equiv u_{p-1}\equiv 2t_{r}u_{r}}$Esto significa que o bien${\displaystyle t_{r}}$o${\displaystyle u_{r}}$es divisible por p . Si es${\displaystyle u_{r}}$, poner${\displaystyle r=2s}$y proceda de manera similar con${\displaystyle 0\equiv 2t_{s}u_{s}}$No todos.${\displaystyle u_{i}}$es divisible por p , para${\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 sostiene y esto significaría que${\displaystyle t_{m}^{2}}$es congruente con un no residuo cuadrático, lo cual es una contradicción. Por lo tanto, este bucle se detiene cuando${\displaystyle t_{l}\equiv 0}$para una l en particular . Esto da${\displaystyle -Du_{l}^{2}\equiv N^{l}}$y porque${\displaystyle -D}$es un residuo cuadrático, l debe ser par. Pon${\displaystyle l=2k}$. Entonces${\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}}$.

${\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}$No es 43, por lo que no deberíamos aplicar el algoritmo en absoluto. La razón por la que el algoritmo no es aplicable es que a=43 es un residuo cuadrático para p=47.

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}}}$.

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 se está 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}}}$.

Resuelve la congruencia${\displaystyle x^{2}\equiv 13{\pmod {17}}}$Para ello, escribe${\displaystyle x^{2}-13=0}$. Primero encuentra un${\displaystyle t_{1}}$y${\displaystyle u_{1}}$de tal manera que${\displaystyle t_{1}^{2}+13u_{1}^{2}}$es un no residuo cuadrático. Tomemos como ejemplo${\displaystyle t_{1}=3,u_{1}=1}$Ahora encuentra.${\displaystyle t_{8}}$,${\displaystyle u_{8}}$mediante computación

${\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}}}$de tal manera que${\displaystyle t_{8}=-68\equiv 0{\pmod {17}},u_{8}=42\equiv 8{\pmod {17}}.}$

Desde${\displaystyle t_{8}=0}$, la ecuación${\displaystyle 0\equiv t_{4}^{2}+13u_{4}^{2}\equiv 7^{2}-13\cdot 3^{2}{\pmod {17}}}$lo que lleva a resolver la ecuación${\displaystyle 3x\equiv \pm 7{\pmod {17}}}$Esto tiene solución${\displaystyle x\equiv \pm 8{\pmod {17}}}$. En efecto,${\displaystyle (\pm 8)^{2}=64\equiv 13{\pmod {17}}}$.