Pocklingtons algoritm

Pocklingtons algoritm är en teknik för att lösa en kongruens av formen

$x^{2}\equiv a{\pmod {p}},$

där x och a är heltal och a är en kvadratisk rest .

Algoritmen är en av de första effektiva metoderna för att lösa en sådan kongruens. Det beskrevs av HC Pocklington 1917.

Algoritmen

(Obs: alla $\equiv$ tolkas som ${\pmod {p}}$ , om inte annat anges.)

Ingångar:

• p , ett udda primtal
• a , ett heltal som är en kvadratisk rest ${\pmod {p}}$ .

Utgångar:

• x , ett heltal som uppfyller $x^{2}\equiv a$ . Observera att om x är en lösning är − x också en lösning och eftersom p är udda, $x\neq -x$ . Så det finns alltid en andra lösning när en hittas.

Lösningsmetod

Pocklington separerar 3 olika fall för p :

Det första fallet, om $p=4m+3$ , med $m\in \mathbb {N}$ , är lösningen ${\ displaystyle x\equiv \pm a^{m+1}}$ .

Det andra fallet, om $p=8m+5$ , med $m\in \mathbb {N}$ och

1. $a^{2m+1}\equiv 1$ , lösningen är $x\equiv \pm a^{m+1}$ .
2. ${\displaystyle a^{2m+1}\equiv -1} , 2$$4^{2m+ 1}\ekvivalent -1$ en (kvadratisk) icke-rest så . Detta betyder att $(4a)^{2m+1}\equiv 1$ så $y\equiv \pm (4a) )^{m+1}$ är en lösning av $y^{2}\equiv 4a$ . Därför $x\equiv \pm y/2$ eller, om y är udda, $x\equiv \pm (p+y)/ 2$ .

Det tredje fallet, om $p=8m+1$ , sätt $D\equiv -a$ , så att ekvationen som ska lösas blir $x^{2}+D\ekvivalent 0$ . Hitta nu genom försök och misstag $t_{1}$ och $u_{1}$ så att $N=t_{1}^{ 2}-Du_{1}^{2}$ är en kvadratisk icke-rest. Dessutom låt

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

Följande jämlikheter gäller nu:

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

Om vi ​​antar att p är av formen $4m+1$ (vilket är sant om p har formen $8m+1$ ), är D en kvadratisk rest och $t_{p}\equiv t_{1}^{p}\equiv t_{1},\quad u_{p}\equiv u_{1}^{p}D^{(p-1)/2}\equiv u_{1}$ . Nu ekvationerna

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

ge en lösning $t_{p-1}\equiv 1,\quad u_{p-1}\equiv 0$ .

Låt $p-1=2r$ . Sedan $0\equiv u_{p-1}\equiv 2t_{r}u_{r}$ . Detta betyder att antingen $t_{r}$ eller $u_{r}$ är delbart med p . Om det är $u_{r}$ , sätt $r=2s$ och fortsätt på liknande sätt med $0\equiv 2t_{s}u_{s}$ . Inte varje $u_{i}$ är delbar med p , för ${\displaystyle u_{1}} .$ är det inte Fallet $u_{m}\equiv 0$ med m udda är omöjligt, eftersom $t_{m}^{2}-Du_{m} ^{2}\equiv N^{m}$ gäller och detta skulle innebära att $t_{m}^{2}$ är kongruent med en kvadratisk icke-rest, vilket är en motsägelse. Så den här slingan stannar när $t_{l}\equiv 0$ för en viss l . Detta ger ${\displaystyle -Du_{l}^{2}\equiv N^{l}} ,$ och eftersom $-D$ är en kvadratisk rest måste l vara jämn . Sätt $l=2k$ . Sedan $0\equiv t_{l}\equiv t_{k}^{2}+Du_{k}^{2}$ . Så lösningen av $x^{2}+D\equiv 0$ fås genom att lösa den linjära kongruensen $u_{k}x\equiv \pm t_ {k}$ .

Exempel

Följande är 4 exempel, motsvarande de 3 olika fallen där Pocklington delade upp former av p . Alla $\equiv$ tas med modulen i exemplet.

Exempel 0

$x^{2}\equiv 43{\pmod {47}}.$

Detta är det första fallet, enligt algoritmen, $x\equiv 43^{(47+1)/2}=43^{12}\ ekv. 2$ , men då $x^{2}=2^{2}=4$ inte 43, så vi bör inte tillämpa algoritmen alls. Anledningen till att algoritmen inte är tillämplig är att a=43 är en kvadratisk icke-rest för p=47.

Exempel 1

Lös kongruensen

$x^{2}\equiv 18{\pmod {23}}.$

Modulen är 23. Detta är $23=4\cdot 5+3$ , så $m=5$ . Lösningen bör vara ${\displaystyle x\equiv \pm 18^{6}\equiv \pm 8{\pmod {23}}} ,$ vilket verkligen är sant: $(\pm 8)^{2}\equiv 64\equiv 18{\pmod {23}}$ .

Exempel 2

Lös kongruensen

$x^{2}\equiv 10{\pmod {13}}.$

Modulen är 13. Detta är $13=8\cdot 1+5$ , så $m=1$ . Verifierar nu $10^{2m+1}\equiv 10^{3}\equiv -1{\pmod {13}}$ . Så lösningen är $x\equiv \pm y/2\equiv \pm (4a)^{2 }/2\equiv \pm 800\equiv \pm 7{\pmod {13}}$ . Detta är verkligen sant: $(\pm 7)^{2}\equiv 49\equiv 10{\pmod {13}}$ .

Exempel 3

Lös kongruensen $x^{2}\equiv 13{\pmod {17}}$ . För detta, skriv $x^{2}-13=0$ . Hitta först a $t_{1}$ och $u_{1}$ så att $t_{1}^{2}+13u_{1} ^{2}$ är en kvadratisk icke-rest. Ta till exempel $t_{1}=3,u_{1}=1$ . Hitta nu $t_{8}$ , $u_{8}$ genom att beräkna

$t_{2}=t_{1}t_{1}+13u_{1}u_{ 1}=9-13=-4\ekvivalent 13{\pmod {17}},$

$u_{2}=t_{1}u_{1}+t_{1}u_{1}=3+3\equiv 6{\pmod {17}}.$

Och på liknande sätt $t_{4}=-299\equiv 7{\pmod {17}},u_{4}= 156\equiv 3{\pmod {17}}$ så att $t_{8}=-68\equiv 0{\pmod {17}},u_{8}=42\equiv 8{\pmod {17}}.$

Eftersom $t_{8}=0$$) {\displaystyle 0\equiv t_{4}^{ 2}+13u_{4}^{2}\equiv 7^{2}-13\cdot 3^{2}{\pmod {17}}}$ är ekvationen vilket leder till att lösa ekvationen $3x\equiv \pm 7{\pmod {17}}$ . Detta har lösning $x\equiv \pm 8{\pmod {17}}$ . Faktum är att $(\pm 8)^{2}=64\equiv 13{\pmod {17}}$ .

• Leonard Eugene Dickson, "History Of Theory Of Numbers" vol 1 s 222, Chelsea Publishing 1952