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

Алгоритм Поклингтона — это техника решения конгруэнтногоуравнения вида
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=t12Du12 не является квадратичнымвычетом. Далее пусть
tn=(t1+u1D)n+(t1u1D)n2

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

um+n=tmun+tnum


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

t1tp1t1+Dup1u1
u1tp1u1+t1up1
 дают решение tp11,up10.
 Пусть p1=2r. Тогда 0up12trur. Этоозначает, что либо tr, либо ur делятся на p. Если делитсяur, положим r=2s и проводим аналогичные выкладки с02tsus. Не все ui делятся на p, так, u1 неделится. Случай um0 с нечётным m невозможен, посколькувыполняется tm2Dum2Nm и это должно означать, чтоtm2 конгруэнтно квадратичному невычету, получили противоречие. Такимобразом, цикла прерывается, когда tl0 для некоторогоl. Это даёт Dul2Nl, а поскольку D являетсяквадратичным вычетом, l должно быть чётным. Положим l=2k.Тогда 0tltk2+Duk2. Таким образом, решениеуравнения 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, такие, чтоt12+13u12 является квадратичным невычетом. Возьмён, например,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, получаем0t42+13u42721332(mod17), чтоведёт к уравнению 3x±7(mod17). Последнее имеет решенияx±8(mod17). Действительно,(±8)2=6413(mod17).