Алгоритм Поклингтона — это техника решения конгруэнтного уравнения вида
где 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 Решаем конгруэнтное уравнение . Запишем уравнение в виде . Сначала найдём и , такие, что является квадратичным невычетом. Возьмён, например, . Найдём , , начав с ,
Продолжим аналогично ,
Поскольку , получаем , что ведёт к уравнению . Последнее имеет решения . Действительно, .
Примечания
Литература
Категория:Модульная арифметика Категория:Теоретико-числовые алгоритмы