Algorytm Pocklingtona

Algorytm Pocklingtona to technika rozwiązywania kongruencji formy

${\ Displaystyle x ^ {2} \ odpowiednik a {\ pmod {p}},}$

gdzie x i a są liczbami całkowitymi, a a jest resztą kwadratową .

Algorytm jest jedną z pierwszych skutecznych metod rozwiązywania takiej kongruencji. Został opisany przez HC Pocklingtona w 1917 roku.

Algorytm

$\$ : wszystkie oznaczają $displaystyle {\ pmod {p}}}$ , chyba że wskazano inaczej.)

Wejścia:

• p , nieparzysta liczba pierwsza
• za , liczba całkowita będąca resztą kwadratową ${\ displaystyle {\ pmod {p}}}$ .

Wyjścia:

• x , liczba całkowita spełniająca wymagania ${\ displaystyle x ^ {2} \ odpowiednik a}$ . Zauważ, że jeśli x jest rozwiązaniem, - x również jest rozwiązaniem, a ponieważ p jest nieparzyste, ${\ displaystyle x \ neq -x}$ . Dlatego zawsze istnieje drugie rozwiązanie, gdy zostanie znalezione.

Metoda rozwiązania

Pocklington rozróżnia 3 różne przypadki dla p :

W pierwszym przypadku, jeśli $displaystyle$$displaystyle x\równoważnik \pm a^{m+1}}$ m $m \ in \ mathbb {$ } ${$ .

W drugim przypadku, jeśli i p $= 8m +$$p$ 5

1. ${\ Displaystyle a ^ {2m + 1} \ równoważnik 1}$ , rozwiązaniem jest ${\ Displaystyle x \ równoważnik \ pm a ^ {m + 1}}$ .
2. ${\ Displaystyle a ^ {2m + 1} \ równoważnik -1}$ , 2 jest (kwadratowym) nieresztą, więc ${\ Displaystyle 4 ^ {2m + 1}\równoważnik -1}$ . Oznacza to, że ${\ Displaystyle (4a) ^ {2m + 1} \ równoważnik 1}$ więc jest rozwiązaniem $displaystyle y ^ {2} \ równoważnik 4a}$$4$ \ Stąd ${\ Displaystyle x \ równoważnik \ pm y / 2}$ lub, jeśli y jest nieparzyste, ${\ Displaystyle x \ równoważnik \ pm (p + y) / 2}$ .

Trzeci przypadek, jeśli $do$$}$$≡$ postać : . $Teraz znajdź$$,$ i i że $_$ . Ponadto niech

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

Zachodzą teraz następujące równości:

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

Załóżmy, że $p$ ma postać $,$ p ma ) D resztą kwadratową i ${\ Displaystyle t_ {p} \ równoważnik t_ {1} ^ {p} \ równoważnik t_ {1}, \ quad u_ {p} \ równoważnik u_ {1} ^ {p} D ^ {(p-1 )/2}\równoważnik u_{1}}$ . Teraz równania

${\ displaystyle t_ {1} \ równoważnik 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}}$

dać rozwiązanie ${\ Displaystyle t_ {p-1} \ równoważnik 1, \ quad u_ {p-1} \ równoważnik 0}$ .

Niech ${\ displaystyle p-1 = 2r}$ . Następnie ${\ displaystyle 0 \ równoważnik u_ {p-1} \ równoważnik 2t_ {r} u_ {r}$ } $Oznacza$ to $,$ albo przez . _ Jeśli $umieść$ , ${\ displaystyle r = 2s}$ i postępuj podobnie z ${\ displaystyle 0 \ równoważnik 2t_ {s} u_ {s}$ } Nie każdy $jest$$podzielny$ przez p bo nie Przypadek z m nieparzystym , ponieważ $u_{m}\equiv 0$${\ Displaystyle t_ {m} ^ {2} -Du_ {m} ^ {2} \ odpowiednik N ^ {m}}$ trzyma się, a to oznaczałoby, że ${\ displaystyle t_ {m} ^ { 2}}$ jest przystające do niereszty kwadratowej, co jest sprzecznością. Zatem ta pętla zatrzymuje $dla$ konkretnego l . Daje to ${\ displaystyle -Du_ {l} ^ {2} \ odpowiednik N ^ {l}}$ i ponieważ ${\ displaystyle -D}$ jest resztą kwadratową, l musi być parzyste. Umieść ${\ displaystyle l = 2k}$ . Następnie ${\ displaystyle 0 \ równoważnik t_ {l} \ równoważnik t_ {k} ^ {2} + Du_ {k} ^ {2}$ } $≡$ rozwiązanie kongruencji ${\ displaystyle u_ {k} x \ odpowiednik \ pm t_ {k}}$ .

Przykłady

Poniżej znajdują się 4 przykłady odpowiadające 3 różnym przypadkom, w których Pocklington podzielił formy p . Wszystko $uwagę$ przy module z przykładu.

Przykład 0

${\ Displaystyle x ^ {2} \ odpowiednik 43 {\ pmod {47}}.}$

Zgodnie z algorytmem jest to pierwszy przypadek, $}$${\ Displaystyle x \ równoważnik 43 ^ {(47 + 1)/2} = 43 ^ {12} \$$.$ , ale wtedy algorytmu Powodem, dla którego algorytm nie ma zastosowania, jest to, że a=43 jest kwadratową niereszta dla p=47.

Przykład 1

Rozwiąż kongruencję

${\ Displaystyle x ^ {2} \ odpowiednik 18 {\ pmod {23}}.}$

Moduł wynosi 23. To $displaystyle$$}$ = m Rozwiązaniem powinno być , co jest rzeczywiście prawdą: $}}$${\ Displaystyle (\ pm 8) ^ {2} \ równoważnik 64 \ równoważnik 18 {\ pmod {23}}$ }

Przykład 2

Rozwiąż kongruencję

${\ Displaystyle x ^ {2} \ odpowiednik 10 {\ pmod {13}}.}$

Moduł wynosi 13. To ${$$1$ \ . Teraz sprawdzam ${\ Displaystyle 10 ^ {2m + 1} \ równoważnik 10 ^ {3} \ równoważnik -1 {\ pmod {13}}$ } Zatem rozwiązaniem jest ${\ Displaystyle x \ równoważnik \ pm y/2 \ równoważnik \ pm (4a) ^ {2}/2 \ równoważnik \ pm 800 \ równoważnik$ . To rzeczywiście prawda: ${\ Displaystyle (\ pm 7) ^ {2} \ równoważnik 49 \ równoważnik 10 {\ pmod {13}}$ }

Przykład 3

Rozwiąż kongruencję. ${\ Displaystyle x ^ {2} \ równoważnik 13 {\ pmod {17}}$ } W tym celu napisz ${\ displaystyle x ^ {2} -13 = 0}$ . $\ displaystyle$ znajdź taki, że a { $i$ u ${1}$ jest nieresztą kwadratową. Weźmy na przykład ${\ displaystyle t_ {1} = 3, u_ {1} = 1}$ . $displaystyle t_ {8}}$ znajdź za pomocą obliczeń t $\$

${\ displaystyle t_ {2} = t_ {1} t_ {1} + 13u_ {1} u_ { 1}=9-13=-4\równoważnik 13{\pmod {17}},}$

${\ Displaystyle u_ {2} = t_ {1} u_ {1} + t_ {1} u_ {1} = 3 + 3 \ równoważnik 6 {\ pmod {17}}.}$

I podobnie ${\ Displaystyle t_ {4} = -299 \ równoważnik 7 {\ pmod {17}}, u_ {4} = 156\równoważnik 3{\pmod {17}}}$ taki, że ${\ Displaystyle t_ {8} = -68 \ równoważnik 0 {\ pmod {17}}, u_ {8} = 42 \ równoważnik 8 {\ pmod {17}}.}$

Ponieważ $równanie$$\ Displaystyle 0 \ równoważnik t_ {4}$ 7 co prowadzi do rozwiązania równania } $}$ To ma rozwiązanie. ${\ Displaystyle x \ równoważnik \ pm 8 {\ pmod {17}}$ } Rzeczywiście ${\ Displaystyle (\ pm 8) ^ {2} = 64 \ równoważnik 13 {\ pmod {17}}}$ .

• Leonard Eugene Dickson, „Historia teorii liczb”, tom 1, s. 222, Chelsea Publishing 1952