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

Алгоритм Поклингтона - это метод решения сравнения вида

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

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

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

Алгоритм

(Примечание: все $\equiv$ воспринимаются как означающие ${\pmod {p}}$, если не указано иное.)

Входы:

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

Выходы:

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

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

Поклингтон выделяет три разных случая для 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}},\qquad 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},\quad u_{m+n}=t_{m}u_{n}+t_{n}u_{m}\quad {\mbox{and}}\quad 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}\quad {\mbox{and}}\quad 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}$ делится на п . Если это $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$ для конкретного л . Это дает $-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}$.

Примеры

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

Пример 0

$x^{2}\equiv 43{\pmod {47}}.$

Это первый случай, согласно алгоритму, $x\equiv 43^{(47+1)/2}=43^{12}\equiv 2$, но тогда $x^{2}=2^{2}=4$ не 43, поэтому нам вообще не следует применять алгоритм. Причина, по которой алгоритм неприменим, заключается в том, что a=43 является квадратичным невычетом для p=47.

Пример 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}}$.

Ссылки

• Леонард Юджин Диксон, «История теории чисел», том 1, стр. 222, Chelsea Publishing, 1952 г.