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

где x и a — целые числа и a является квадратичным вычетом.
Алгоритм является одним из первых эффективных методов решения такого уравнения. Алгоритм описал Г.К. Поклингтон[англ.] в 1917 году[1].
Алгоритм
(Замечание: Все знаки
означают
, если не сказано другое.)
Вход:
- p, нечётное простое число
- a, целое число, являющееся двоичным вычетом
.
Выход:
- x, целое число, удовлетворяющее тождеству
. Заметим, что если x является решением, то −x также является решением и, поскольку p нечётно,
. Таким образом, всегда существует второе решение, если хотя бы одно найдено.
Метод решения
Поклингтон рассматривает 3 различных случая для p:
Первый случай, если
, с
, решение равно
.
Второй случай, если
, с
и
, решение равно
.
, 2 не является (квадратичным) вычетом, так что
. Это означает, что
, так что
является решением
. Следовательно,
или, если y нечётно,
.
Третий случай, если
, положим
, так что уравнение превращается в
. Теперь методом проб и ошибок находим
и
, такие, что
не является квадратичным вычетом. Далее пусть

.
Теперь выполняются следующие равенства:


.
Если p имеет вид
(что верно, если p имеет вид
), D является квадратичным вычетом и
. Теперь равенства


дают решение
.
Пусть
. Тогда
. Это означает, что либо
, либо
делятся на p. Если делится
, положим
и проводим аналогичные выкладки с
. Не все
делятся на p, так,
не делится. Случай
с нечётным m невозможен, поскольку выполняется
и это должно означать, что
конгруэнтно квадратичному невычету, получили противоречие. Таким образом, цикла прерывается, когда
для некоторого l. Это даёт
, а поскольку
является квадратичным вычетом, l должно быть чётным. Положим
. Тогда
. Таким образом, решение уравнения
получаем путём решения линейного уравнения
.
Примеры
Ниже приведены 3 примера, соответствующие 3 различным случаям. В примерах все знаки
означает сравнение по модулю.
Пример 1
Решаем конгруэнтное уравнение

Модуль равен 23. Поскольку
,
. Решениями должны быть значения
, и это действительно решения:
.
Пример 2
Решаем конгруэнтное уравнение

Модуль равен 13. Поскольку
,
. Проверяем, что
. Таким образом, решением будет
. И это действительно решения:
.
Пример 3
Решаем конгруэнтное уравнение
. Запишем уравнение в виде
. Сначала найдём
и
, такие, что
является квадратичным невычетом. Возьмён, например,
. Найдём
,
, начав с
,
Продолжим аналогично
, 
Поскольку
, получаем
, что ведёт к уравнению
. Последнее имеет решения
. Действительно,
.
Примечания
Литература
- H.C. Pocklington. Тhe direct solution of the quadratic and cubic binomial congruences with prime moduli // Proceedings of the Cambridge Philosophical Society. — 1917. — Т. 19.