Алгоритм Поклингтона (Glikjnmb Hktlnuimkug)

Перейти к навигации Перейти к поиску

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

где x и a — целые числа и a является квадратичным вычетом.

Алгоритм является одним из первых эффективных методов решения такого уравнения. Алгоритм описал Г.К. Поклингтон[англ.] в 1917 году[1].

(Замечание: Все знаки означают , если не сказано другое.)

Вход:

  • p, нечётное простое число
  • a, целое число, являющееся двоичным вычетом .

Выход:

  • x, целое число, удовлетворяющее тождеству . Заметим, что если x является решением, то −x также является решением и, поскольку p нечётно, . Таким образом, всегда существует второе решение, если хотя бы одно найдено.

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

[править | править код]

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

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

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

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

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

.

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

.

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

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

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

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

Решаем конгруэнтное уравнение

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

Решаем конгруэнтное уравнение

Модуль равен 13. Поскольку , . Проверяем, что . Таким образом, решением будет . И это действительно решения: .

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

,

Продолжим аналогично ,

Поскольку , получаем , что ведёт к уравнению . Последнее имеет решения . Действительно, .

Примечания

[править | править код]
  1. Pocklington, 1917, с. 57–58.

Литература

[править | править код]
  • H.C. Pocklington. Тhe direct solution of the quadratic and cubic binomial congruences with prime moduli // Proceedings of the Cambridge Philosophical Society. — 1917. — Т. 19.