Алгоритм Поклингтона

Алгоритм Поклингтона — это техника решения конгруэнтного уравнения вида

$x^2\equiv <!--\; \equiv \; -->a(\mathrm{mod}p),$$x^{2}\equiv a{\pmod {p}},\,$

где x и a — целые числа и a является квадратичным вычетом.

Алгоритм является одним из первых эффективных методов решения такого уравнения. Алгоритм описал Г.К. Поклингтон^[en] в 1917 году.

АлгоритмПравить

(Замечание: Все знаки $\equiv <!--\; \equiv \; -->$$\equiv$  означают $(\mathrm{mod}p)$$\pmod p$ , если не сказано другое.)

Вход:

• p, нечётное простое число
• a, целое число, являющееся двоичным вычетом $(\mathrm{mod}p)$$\pmod p$ .

Выход:

• x, целое число, удовлетворяющее тождеству $x^2\equiv <!--\; \equiv \; -->a$$x^{2}\equiv a$ . Заметим, что если x является решением, то −x также является решением и, поскольку p нечётно, $x\ne <!--\; \ne \; -->-<!--\; -\; -->x$$x\neq -x$ . Таким образом, всегда существует второе решение, если хотя бы одно найдено.

Метод решенияПравить

Поклингтон рассматривает 3 различных случая для p:

Первый случай, если $p=4m+3$$p=4m+3$ , с $m\in <!--\; \in \; -->\mathbb{N}$$m \in \mathbb{N}$ , решение равно $x\equiv <!--\; \equiv \; -->\pm <!--\; \pm \; -->a^{m+1}$$x\equiv \pm a^{m+1}$ .

Второй случай, если $p=8m+5$$p=8m+5$ , с $m\in <!--\; \in \; -->\mathbb{N}$$m \in \mathbb{N}$  и

1. $a^{2m+1}\equiv <!--\; \equiv \; -->1$$a^{2m+1}\equiv 1$ , решение равно $x\equiv <!--\; \equiv \; -->\pm <!--\; \pm \; -->a^{m+1}$$x\equiv \pm a^{m+1}$ .
2. $a^{2m+1}\equiv <!--\; \equiv \; -->-<!--\; -\; -->1$$a^{2m+1}\equiv -1$ , 2 не является (квадратичным) вычетом, так что $4^{2m+1}\equiv <!--\; \equiv \; -->-<!--\; -\; -->1$$4^{2m+1}\equiv -1$ . Это означает, что $(4a{)}^{2m+1}\equiv <!--\; \equiv \; -->1$$(4a)^{2m+1}\equiv 1$ , так что $y\equiv <!--\; \equiv \; -->\pm <!--\; \pm \; -->(4a{)}^{m+1}$$y\equiv \pm (4a)^{m+1}$  является решением $y^2\equiv <!--\; \equiv \; -->4a$$y^{2}\equiv 4a$ . Следовательно, $x\equiv <!--\; \equiv \; -->\pm <!--\; \pm \; -->y/2$$x\equiv \pm y/2$  или, если y нечётно, $x\equiv <!--\; \equiv \; -->\pm <!--\; \pm \; -->(p+y)/2$$x\equiv \pm (p+y)/2$ .

Третий случай, если $p=8m+1$$p=8m+1$ , положим $D\equiv <!--\; \equiv \; -->-<!--\; -\; -->a$$D\equiv -a$ , так что уравнение превращается в $x^2+D\equiv <!--\; \equiv \; -->0$$x^{2}+D\equiv 0$ . Теперь методом проб и ошибок находим $t_1$$t_{1}$  и $u_1$$u_{1}$ , такие, что $N=t_1^2-<!--\; -\; -->D{u}_1^2$$N=t_{1}^{2}-Du_{1}^{2}$  не является квадратичным вычетом. Далее пусть

$t_n=\frac{(t_1+u_1\sqrt{D}{)}^n+(t_1-<!--\; -\; -->u_1\sqrt{D}{)}^n}{2}$$t_{n}={\frac {(t_{1}+u_{1}{\sqrt {D}})^{n}+(t_{1}-u_{1}{\sqrt {D}})^{n}}{2}}$ 

$u_n=\frac{(t_1+u_1\sqrt{D}{)}^n-<!--\; -\; -->(t_1-<!--\; -\; -->u_1\sqrt{D}{)}^n}{2\sqrt{D}}$$u_{n}={\frac {(t_{1}+u_{1}{\sqrt {D}})^{n}-(t_{1}-u_{1}{\sqrt {D}})^{n}}{2{\sqrt {D}}}}$ .

Теперь выполняются следующие равенства:

$t_{m+n}=t_m{t}_n+D{u}_m{u}_n$$t_{m+n}=t_{m}t_{n}+Du_{m}u_{n}$ 

$u_{m+n}=t_m{u}_n+t_n{u}_m$$u_{m+n}=t_{m}u_{n}+t_{n}u_{m}$ 

$t_n^2-<!--\; -\; -->D{u}_n^2=N^n$$t_{n}^{2}-Du_{n}^{2}=N^{n}$ .

Если p имеет вид $4m+1$$4m+1$  (что верно, если p имеет вид $8m+1$$8m+1$ ), D является квадратичным вычетом и $t_p\equiv <!--\; \equiv \; -->t_1^p\equiv <!--\; \equiv \; -->t_1,u_p\equiv <!--\; \equiv \; -->u_1^p{D}^{(p-<!--\; -\; -->1)/2}\equiv <!--\; \equiv \; -->u_1$$t_{p}\equiv t_{1}^{p}\equiv t_{1},\quad u_{p}\equiv u_{1}^{p}D^{(p-1)/2}\equiv u_{1}$ . Теперь равенства

$t_1\equiv <!--\; \equiv \; -->t_{p-<!--\; -\; -->1}{t}_1+D{u}_{p-<!--\; -\; -->1}{u}_1$$t_{1}\equiv t_{p-1}t_{1}+Du_{p-1}u_{1}$ 

$u_1\equiv <!--\; \equiv \; -->t_{p-<!--\; -\; -->1}{u}_1+t_1{u}_{p-<!--\; -\; -->1}$$u_{1}\equiv t_{p-1}u_{1}+t_{1}u_{p-1}$ 

дают решение $t_{p-<!--\; -\; -->1}\equiv <!--\; \equiv \; -->1,u_{p-<!--\; -\; -->1}\equiv <!--\; \equiv \; -->0$$t_{p-1}\equiv 1,\quad u_{p-1}\equiv 0$ .

Пусть $p-<!--\; -\; -->1=2r$$p-1=2r$ . Тогда $0\equiv <!--\; \equiv \; -->u_{p-<!--\; -\; -->1}\equiv <!--\; \equiv \; -->2t_r{u}_r$$0\equiv u_{p-1}\equiv 2t_{r}u_{r}$ . Это означает, что либо $t_r$$t_{r}$ , либо $u_r$$u_{r}$  делятся на p. Если делится $u_r$$u_{r}$ , положим $r=2s$$r=2s$  и проводим аналогичные выкладки с $0\equiv <!--\; \equiv \; -->2t_s{u}_s$$0\equiv 2t_{s}u_{s}$ . Не все $u_i$$u_{i}$  делятся на p, так, $u_1$$u_{1}$  не делится. Случай $u_m\equiv <!--\; \equiv \; -->0$$u_{m}\equiv 0$  с нечётным m невозможен, поскольку выполняется $t_m^2-<!--\; -\; -->D{u}_m^2\equiv <!--\; \equiv \; -->N^m$$t_{m}^{2}-Du_{m}^{2}\equiv N^{m}$  и это должно означать, что $t_m^2$$t_{m}^{2}$  конгруэнтно квадратичному невычету, получили противоречие. Таким образом, цикла прерывается, когда $t_l\equiv <!--\; \equiv \; -->0$$t_{l}\equiv 0$  для некоторого l. Это даёт $-<!--\; -\; -->D{u}_l^2\equiv <!--\; \equiv \; -->N^l$$-Du_{l}^{2}\equiv N^{l}$ , а поскольку $-<!--\; -\; -->D$$-D$  является квадратичным вычетом, l должно быть чётным. Положим $l=2k$$l=2k$ . Тогда $0\equiv <!--\; \equiv \; -->t_l\equiv <!--\; \equiv \; -->t_k^2+D{u}_k^2$$0\equiv t_{l}\equiv t_{k}^{2}+Du_{k}^{2}$ . Таким образом, решение уравнения $x^2+D\equiv <!--\; \equiv \; -->0$$x^{2}+D\equiv 0$  получаем путём решения линейного уравнения $u_{k}x\equiv <!--\; \equiv \; -->\pm <!--\; \pm \; -->t_k$$u_{k}x\equiv \pm t_{k}$ .

ПримерыПравить

Ниже приведены 3 примера, соответствующие 3 различным случаям. В примерах все знаки $\equiv <!--\; \equiv \; -->$$\equiv$  означает сравнение по модулю.

Пример 1Править

Решаем конгруэнтное уравнение

$x^2\equiv <!--\; \equiv \; -->18(\mathrm{mod}23).$$x^{2}\equiv 18{\pmod {23}}.$ 

Модуль равен 23. Поскольку $23=4\cdot <!--\; \cdot \; -->5+3$$23=4\cdot 5+3$ , $m=5$$m=5$ . Решениями должны быть значения $x\equiv <!--\; \equiv \; -->\pm <!--\; \pm \; -->{18}^6\equiv <!--\; \equiv \; -->\pm <!--\; \pm \; -->8(\mathrm{mod}23)$$x\equiv \pm 18^{6}\equiv \pm 8{\pmod {23}}$ , и это действительно решения: $(\pm <!--\; \pm \; -->8{)}^2\equiv <!--\; \equiv \; -->64\equiv <!--\; \equiv \; -->18(\mathrm{mod}23)$$(\pm 8)^{2}\equiv 64\equiv 18{\pmod {23}}$ .

Пример 2Править

Решаем конгруэнтное уравнение

$x^2\equiv <!--\; \equiv \; -->10(\mathrm{mod}13).$$x^{2}\equiv 10{\pmod {13}}.$ 

Модуль равен 13. Поскольку $13=8\cdot <!--\; \cdot \; -->1+5$$13=8\cdot 1+5$ , $m=1$$m=1$ . Проверяем, что ${10}^{2m+1}\equiv <!--\; \equiv \; -->{10}^3\equiv <!--\; \equiv \; -->-<!--\; -\; -->1(\mathrm{mod}13)$$10^{2m+1}\equiv 10^{3}\equiv -1{\pmod {13}}$ . Таким образом, решением будет $x\equiv <!--\; \equiv \; -->\pm <!--\; \pm \; -->y/2\equiv <!--\; \equiv \; -->\pm <!--\; \pm \; -->(4a{)}^2/2\equiv <!--\; \equiv \; -->\pm <!--\; \pm \; -->800\equiv <!--\; \equiv \; -->\pm <!--\; \pm \; -->7(\mathrm{mod}13)$$x\equiv \pm y/2\equiv \pm (4a)^{2}/2\equiv \pm 800\equiv \pm 7{\pmod {13}}$ . И это действительно решения: $(\pm <!--\; \pm \; -->7{)}^2\equiv <!--\; \equiv \; -->49\equiv <!--\; \equiv \; -->10(\mathrm{mod}13)$$(\pm 7)^{2}\equiv 49\equiv 10{\pmod {13}}$ .

Пример 3Править

Решаем конгруэнтное уравнение $x^2\equiv <!--\; \equiv \; -->13(\mathrm{mod}17)$$x^{2}\equiv 13{\pmod {17}}$ . Запишем уравнение в виде $x^2-<!--\; -\; -->13=0$$x^{2}-13=0$ . Сначала найдём $t_1$$t_{1}$  и $u_1$$u_{1}$ , такие, что $t_1^2+13u_1^2$$t_{1}^{2}+13u_{1}^{2}$  является квадратичным невычетом. Возьмён, например, $t_1=3,u_1=1$$t_{1}=3,u_{1}=1$ . Найдём $t_8$$t_{8}$ , $u_8$$u_{8}$ , начав с

$t_2=t_1{t}_1+13u_1{u}_1=9-<!--\; -\; -->13=-<!--\; -\; -->4\equiv <!--\; \equiv \; -->13(\mathrm{mod}17),$$t_{2}=t_{1}t_{1}+13u_{1}u_{1}=9-13=-4\equiv 13{\pmod {17}},\,$ ,

$u_2=t_1{u}_1+t_1{u}_1=3+3\equiv <!--\; \equiv \; -->6(\mathrm{mod}17).$$u_{2}=t_{1}u_{1}+t_{1}u_{1}=3+3\equiv 6{\pmod {17}}.\,$ 

Продолжим аналогично $t_4=-<!--\; -\; -->299\equiv <!--\; \equiv \; -->7(\mathrm{mod}17)u_4=156\equiv <!--\; \equiv \; -->3(\mathrm{mod}17)$$t_{4}=-299\equiv 7{\pmod {17}}\,u_{4}=156\equiv 3{\pmod {17}}$ , $t_8=-<!--\; -\; -->68\equiv <!--\; \equiv \; -->0(\mathrm{mod}17)u_8=42\equiv <!--\; \equiv \; -->8(\mathrm{mod}17).$$t_{8}=-68\equiv 0{\pmod {17}}\,u_{8}=42\equiv 8{\pmod {17}}.$ 

Поскольку $t_8=0$$t_{8}=0$ , получаем $0\equiv <!--\; \equiv \; -->t_4^2+13u_4^2\equiv <!--\; \equiv \; -->7^2-<!--\; -\; -->13\cdot <!--\; \cdot \; -->3^2(\mathrm{mod}17)$$0\equiv t_{4}^{2}+13u_{4}^{2}\equiv 7^{2}-13\cdot 3^{2}{\pmod {17}}$ , что ведёт к уравнению $3x\equiv <!--\; \equiv \; -->\pm <!--\; \pm \; -->7(\mathrm{mod}17)$$3x\equiv \pm 7{\pmod {17}}$ . Последнее имеет решения $x\equiv <!--\; \equiv \; -->\pm <!--\; \pm \; -->8(\mathrm{mod}17)$$x\equiv \pm 8{\pmod {17}}$ . Действительно, $(\pm <!--\; \pm \; -->8{)}^2=64\equiv <!--\; \equiv \; -->13(\mathrm{mod}17)$$(\pm 8)^{2}=64\equiv 13{\pmod {17}}$ .