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

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

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

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

Алгоритм

( Замечание : Все знаки ${\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 }$ означает сравнение по модулю .

Пример 1

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

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

Пример 2

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

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

Пример 3

Решаем конгруэнтное уравнение ${\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}}}$ .

Примечания

Литература