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

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

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

Алгоритм


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

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

Выход:

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

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


 Поклингтон рассматривает 3 различных случая для p:
 Первый случай, если p=4m+3, с mN, решение равно x±am+1.
 Второй случай, если p=8m+5, с mN и

  1. a2m+11, решение равно x±am+1.
  2. a2m+11, 2 не является (квадратичным) вычетом, так что 42m+11. Это означает, что (4a)2m+11, так что y±(4a)m+1 является решением y24a. Следовательно, x±y/2 или, если y нечётно, x±(p+y)/2.

 Третий случай, если p=8m+1, положим Da, так что уравнение превращается в x2+D0. Теперь методом проб и ошибок находим t1 и u1, такие, что N=t21Du21 не является квадратичным вычетом. Далее пусть
tn=(t1+u1D)n+(t1u1D)n2

un=(t1+u1D)n(t1u1D)n2D
. Теперь выполняются следующие равенства:
tm+n=tmtn+Dumun

um+n=tmun+tnum


t2nDu2n=Nn.
  Если p имеет вид 4m+1 (что верно, если p имеет вид 8m+1), D является квадратичным вычетом и tptp1t1,upup1D(p1)/2u1. Теперь равенства

t1tp1t1+Dup1u1
u1tp1u1+t1up1
  дают решение tp11,up10.
 Пусть p1=2r. Тогда 0up12trur. Это означает, что либо tr, либо ur делятся на p. Если делится ur, положим r=2s и проводим аналогичные выкладки с 02tsus. Не все ui делятся на p, так, u1 не делится. Случай um0 с нечётным m невозможен, поскольку выполняется t2mDu2mNm и это должно означать, что t2m конгруэнтно квадратичному невычету, получили противоречие. Таким образом, цикла прерывается, когда tl0 для некоторого l. Это даёт Du2lNl, а поскольку D является квадратичным вычетом, l должно быть чётным. Положим l=2k. Тогда 0tlt2k+Du2k. Таким образом, решение уравнения x2+D0 получаем путём решения линейного уравнения ukx±tk.

Примеры


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

Пример 1


 Решаем конгруэнтное уравнение
x218(mod23).
Модуль равен 23. Поскольку 23=45+3, m=5. Решениями должны быть значения x±186±8(mod23), и это действительно решения: (±8)26418(mod23).

Пример 2


 Решаем конгруэнтное уравнение
x210(mod13).
Модуль равен 13. Поскольку 13=81+5, m=1. Проверяем, что 102m+11031(mod13). Таким образом, решением будет x±y/2±(4a)2/2±800±7(mod13). И это действительно решения: (±7)24910(mod13).

Пример 3


 Решаем конгруэнтное уравнение x213(mod17). Запишем уравнение в виде x213=0. Сначала найдём t1 и u1, такие, что t21+13u21 является квадратичным невычетом. Возьмён, например, t1=3,u1=1. Найдём t8, u8, начав с
t2=t1t1+13u1u1=913=413(mod17),
,
u2=t1u1+t1u1=3+36(mod17).
Продолжим аналогично t4=2997(mod17)u4=1563(mod17), t8=680(mod17)u8=428(mod17).
 Поскольку t8=0, получаем 0t24+13u24721332(mod17), что ведёт к уравнению 3x±7(mod17). Последнее имеет решения x±8(mod17). Действительно, (±8)2=6413(mod17).