Алгоритм Поклингтона
— это техника решения конгруэнтного уравнения вида
-
где
x
и
a
— целые числа и
a
является
квадратичным вычетом
.
Алгоритм является одним из первых эффективных методов решения такого уравнения. Алгоритм описал
в 1917 году
.
Алгоритм
(
Замечание
: Все знаки
означают
, если не сказано другое.)
Вход:
-
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
.