Меню Главная Случайная статья Настройки Алгоритм Поклингтона Материал из https://ru.wikipedia.org Алгоритм Поклингтона — это техника решения конгруэнтного уравнения вида ${\displaystyle x^{2}\equiv a{\pmod {p}},\,}$ где x и a — целые числа и a является квадратичным вычетом. Алгоритм является одним из первых эффективных методов решения такого уравнения. Алгоритм описал Г.К. Поклингтон[англ.] в 1917 году[1]. Содержание 1 Алгоритм 1.1 Метод решения 2 Примеры 2.1 Пример 1 2.2 Пример 2 2.3 Пример 3 3 Примечания 4 Литература Алгоритм (Замечание: Все знаки ${\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} }$ и ${\displaystyle a^{2m+1}\equiv 1}$, решение равно ${\displaystyle x\equiv \pm a^{m+1}}$. ${\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}}}$. Примечания Pocklington, 1917, с. 57–58. Литература H.C. Pocklington. Тhe direct solution of the quadratic and cubic binomial congruences with prime moduli // Proceedings of the Cambridge Philosophical Society. — 1917. — Т. 19.