Interested Article - Алгоритм Поклингтона

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

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

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

Алгоритм

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

Вход:

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

Выход:

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

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

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

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

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

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

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

.

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

.

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

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

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

Примеры

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

Пример 1

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

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

Пример 2

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

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

Пример 3

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

,

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

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

Примечания

  1. , с. 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 .


Источник —

Same as Алгоритм Поклингтона