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

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

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

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

Алгоритм

(Примечание: все означают , если не указано иное.)

Входы:

  • п, странный основной
  • а, целое число, которое является квадратичным вычетом .

Выходы:

  • Икс, целое число, удовлетворяющее . Обратите внимание, что если Икс это решение, -Икс это тоже решение, и поскольку п странно, . Так что всегда есть второе решение, когда оно найдено.

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

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

Первый случай, если , с , решение .

Второй случай, если , с и

  1. , решение .
  2. , 2 является (квадратичным) невычетом, поэтому . Это означает, что так это решение . Следовательно или если у странно, .

Третий случай, если , положить , поэтому уравнение для решения принимает вид . Теперь найди методом проб и ошибок и так что является квадратичным невычетом. Кроме того, пусть

.

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

.

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

дать решение .

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

Примеры

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

Пример 0

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

Пример 1

Решите сравнение

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

Пример 2

Решите сравнение

Модуль равен 13. Это , так . Сейчас проверяю . Итак, решение . Это действительно правда: .

Пример 3

Решите сравнение . Для этого напишите . Сначала найдите и такой, что является квадратичным невычетом. Взять к примеру . Теперь найди , вычисляя

И аналогично такой, что

С , уравнение что приводит к решению уравнения . У этого есть решение . В самом деле, .

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

  • Леонард Юджин Диксон, "История теории чисел", том 1, стр. 222, Chelsea Publishing, 1952 г.
  1. ^ H.C. Поклингтон, Труды Кембриджского философского общества, том 19, страницы 57–58