Алгоритм Поклингтона - Pocklingtons algorithm - Wikipedia

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

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

куда Икс и а целые числа и а это квадратичный вычет.

Алгоритм является одним из первых эффективных методов решения такого сравнения. Это было описано H.C. Pocklington в 1917 г.^[1]

Алгоритм

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

Входы:

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

Выходы:

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

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

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

Первый случай, если ${\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}$ или если у странно, ${\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}},\qquad 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},\quad u_{m+n}=t_{m}u_{n}+t_{n}u_{m}\quad {\mbox{and}}\quad t_{n}^{2}-Du_{n}^{2}=N^{n}}$.

Предполагая, что п имеет форму ${\displaystyle 4m+1}$ (что верно, если п имеет форму ${\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}\quad {\mbox{and}}\quad 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}}$ делится на п. Если это ${\displaystyle u_{r}}$, положить ${\displaystyle r=2s}$ и поступаем аналогично с ${\displaystyle 0\equiv 2t_{s}u_{s}}$. Не каждый ${\displaystyle u_{i}}$ делится на п, за ${\displaystyle u_{1}}$ не является. Дело ${\displaystyle u_{m}\equiv 0}$ с м странно невозможно, потому что ${\displaystyle t_{m}^{2}-Du_{m}^{2}\equiv N^{m}}$ держит, и это будет означать, что ${\displaystyle t_{m}^{2}}$ конгруэнтно квадратичному невычету; противоречие. Итак, этот цикл останавливается, когда ${\displaystyle t_{l}\equiv 0}$ для конкретного л. Это дает ${\displaystyle -Du_{l}^{2}\equiv N^{l}}$, и потому что ${\displaystyle -D}$ квадратичный вычет, л должно быть даже. Положить ${\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}}$.

Примеры

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

Пример 0

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

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

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

Рекомендации

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

1. H.C. Поклингтон, Труды Кембриджского философского общества, том 19, страницы 57–58