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

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

$x^2\equiv a(\mathrm{mod}p),$

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

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

Алгоритм

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

Вход:

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

Выход:

• x, целое число, удовлетворяющее тождеству $x^2\equiv a$. Заметим, что если x является решением, то −x также является решением и, поскольку p нечётно, $x\ne -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-D{u}_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+D{u}_m{u}_n$

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

$t_n^2-D{u}_n^2=N^n$.

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

$t_1\equiv t_{p-1}{t}_1+D{u}_{p-1}{u}_1$

$u_1\equiv t_{p-1}{u}_1+t_1{u}_{p-1}$

дают решение $t_{p-1}\equiv 1,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-D{u}_m^2\equiv N^m$ и это должно означать, что $t_m^2$ конгруэнтно квадратичному невычету, получили противоречие. Таким образом, цикла прерывается, когда $t_l\equiv 0$ для некоторого l. Это даёт $-D{u}_l^2\equiv N^l$, а поскольку $-D$ является квадратичным вычетом, l должно быть чётным. Положим $l=2k$. Тогда $0\equiv t_l\equiv t_k^2+D{u}_k^2$. Таким образом, решение уравнения $x^2+D\equiv 0$ получаем путём решения линейного уравнения $u_{k}x\equiv \pm t_k$.

Примеры

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

Пример 1

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

$x^2\equiv 18(\mathrm{mod}23).$

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

Пример 2

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

$x^2\equiv 10(\mathrm{mod}13).$

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

Пример 3

Решаем конгруэнтное уравнение $x^2\equiv 13(\mathrm{mod}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(\mathrm{mod}17),$,

$u_2=t_1{u}_1+t_1{u}_1=3+3\equiv 6(\mathrm{mod}17).$

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

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

Литература

• Шаблон:Статья