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

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

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

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

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

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

Вход:

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

Выход:

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

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

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

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

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

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

${\displaystyle t_{n}={\frac {(t_{1}+u_{1}{\sqrt {D}})^{n}+(t_{1}-u_{1}{\sqrt {D}})^{n}}{2}}}$

${\displaystyle u_{n}={\frac {(t_{1}+u_{1}{\sqrt {D}})^{n}-(t_{1}-u_{1}{\sqrt {D}})^{n}}{2{\sqrt {D}}}}}$.

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

${\displaystyle t_{m+n}=t_{m}t_{n}+Du_{m}u_{n}}$

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

У этой статьи есть несколько проблем, помогите их исправить: Необходимо проверить качество перевода c неуказанного языка, исправить содержательные и стилистические ошибки. Вы можете помочь улучшить эту статью (см. также рекомендации по переводу). Оригинал не указан. Пожалуйста, укажите его. (29 июня 2017) Стиль этой статьи неэнциклопедичен или нарушает нормы литературного русского языка. Статью следует исправить согласно стилистическим правилам Википедии. (29 июня 2017) Пожалуйста, после исправления проблемы исключите её из списка параметров. После устранения всех недостатков этот шаблон может быть удалён любым участником.