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

куда Икс и а целые числа и а это квадратичный вычет.
Алгоритм является одним из первых эффективных методов решения такого сравнения. Это было описано H.C. Pocklington в 1917 г.[1]
Алгоритм
(Примечание: все
означают
, если не указано иное.)
Входы:
- п, странный основной
- а, целое число, которое является квадратичным вычетом
.
Выходы:
- Икс, целое число, удовлетворяющее
. Обратите внимание, что если Икс это решение, -Икс это тоже решение, и поскольку п странно,
. Так что всегда есть второе решение, когда оно найдено.
Метод решения
Поклингтон выделяет 3 разных случая для п:
Первый случай, если
, с
, решение
.
Второй случай, если
, с
и
, решение
.
, 2 является (квадратичным) невычетом, поэтому
. Это означает, что
так
это решение
. Следовательно
или если у странно,
.
Третий случай, если
, положить
, поэтому уравнение для решения принимает вид
. Теперь найди методом проб и ошибок
и
так что
является квадратичным невычетом. Кроме того, пусть
.
Теперь выполняются следующие равенства:
.
Предполагая, что п имеет форму
(что верно, если п имеет форму
), D является квадратичным вычетом и
. Теперь уравнения

дать решение
.
Позволять
. потом
. Это означает, что либо
или же
делится на п. Если это
, положить
и поступаем аналогично с
. Не каждый
делится на п, за
не является. Дело
с м странно невозможно, потому что
держит, и это будет означать, что
конгруэнтно квадратичному невычету; противоречие. Итак, этот цикл останавливается, когда
для конкретного л. Это дает
, и потому что
квадратичный вычет, л должно быть даже. Положить
. потом
. Итак, решение
получается путем решения линейного сравнения
.
Примеры
Ниже приведены 4 примера, соответствующие 3 различным случаям, в которых Поклингтон разделил формы п. Все
взяты с модуль в примере.
Пример 0

Это первый случай, согласно алгоритму,
, но потом
не 43, поэтому алгоритм вообще не следует применять. Причина, по которой алгоритм неприменим, заключается в том, что a = 43 является квадратичным невычетом для p = 47.
Пример 1
Решите сравнение

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

Модуль равен 13. Это
, так
. Сейчас проверяю
. Итак, решение
. Это действительно правда:
.
Пример 3
Решите сравнение
. Для этого напишите
. Сначала найдите
и
такой, что
является квадратичным невычетом. Взять к примеру
. Теперь найди
,
вычисляя


И аналогично
такой, что 
С
, уравнение
что приводит к решению уравнения
. У этого есть решение
. В самом деле,
.
Рекомендации
- Леонард Юджин Диксон, "История теории чисел", том 1, стр. 222, Chelsea Publishing, 1952 г.
- ^ H.C. Поклингтон, Труды Кембриджского философского общества, том 19, страницы 57–58