Алгоритм Поклингтона (Glikjnmb Hktlnuimkug)

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

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

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

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

Алгоритм

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

Вход:

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

Выход:

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

Метод решения

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

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

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

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

Третий случай, если $p=8m+1$, положим $D\equiv -a$, так что уравнение превращается в $x^{2}+D\equiv 0$. Теперь методом проб и ошибок находим $t_{1}$ и $u_{1}$, такие, что $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}}$

$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}+Du_{m}u_{n}$

$u_{m+n}=t_{m}u_{n}+t_{n}u_{m}$

$t_{n}^{2}-Du_{n}^{2}=N^{n}$.

Если p имеет вид $4m+1$ (что верно, если p имеет вид $8m+1$), D является квадратичным вычетом и $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 t_{p-1}t_{1}+Du_{p-1}u_{1}$

$u_{1}\equiv t_{p-1}u_{1}+t_{1}u_{p-1}$

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

Пусть $p-1=2r$. Тогда $0\equiv u_{p-1}\equiv 2t_{r}u_{r}$. Это означает, что либо $t_{r}$, либо $u_{r}$ делятся на p. Если делится $u_{r}$, положим $r=2s$ и проводим аналогичные выкладки с $0\equiv 2t_{s}u_{s}$. Не все $u_{i}$ делятся на p, так, $u_{1}$ не делится. Случай $u_{m}\equiv 0$ с нечётным m невозможен, поскольку выполняется $t_{m}^{2}-Du_{m}^{2}\equiv N^{m}$ и это должно означать, что $t_{m}^{2}$ конгруэнтно квадратичному невычету, получили противоречие. Таким образом, цикла прерывается, когда $t_{l}\equiv 0$ для некоторого l. Это даёт $-Du_{l}^{2}\equiv N^{l}$, а поскольку $-D$ является квадратичным вычетом, l должно быть чётным. Положим $l=2k$. Тогда $0\equiv t_{l}\equiv t_{k}^{2}+Du_{k}^{2}$. Таким образом, решение уравнения $x^{2}+D\equiv 0$ получаем путём решения линейного уравнения $u_{k}x\equiv \pm t_{k}$.

Примеры

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

Пример 1

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

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

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

Пример 2

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

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

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

Пример 3

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

$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 6{\pmod {17}}.\,$

Продолжим аналогично $t_{4}=-299\equiv 7{\pmod {17}}\,u_{4}=156\equiv 3{\pmod {17}}$, $t_{8}=-68\equiv 0{\pmod {17}}\,u_{8}=42\equiv 8{\pmod {17}}.$

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