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

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

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

Алгоритм


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

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

Выход:

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

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


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

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

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

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

um+n=tmun+tnum
um+n=tmun+tnum


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

t1tp1t1+Dup1u1t1tp1t1+Dup1u1
u1tp1u1+t1up1u1tp1u1+t1up1
 дают решение tp11,up10tp11,up10.
 Пусть p1=2rp1=2r. Тогда 0up12trur0up12trur. Этоозначает, что либо trtr, либо urur делятся на p. Если делитсяurur, положим r=2sr=2s и проводим аналогичные выкладки с02tsus02tsus. Не все uiui делятся на p, так, u1u1 неделится. Случай um0um0 с нечётным m невозможен, посколькувыполняется t2mDu2mNmt2mDu2mNm и это должно означать, чтоt2mt2m конгруэнтно квадратичному невычету, получили противоречие. Такимобразом, цикла прерывается, когда tl0tl0 для некоторогоl. Это даёт Du2lNlDu2lNl, а поскольку DD являетсяквадратичным вычетом, l должно быть чётным. Положим l=2kl=2k.Тогда 0tlt2k+Du2k0tlt2k+Du2k. Таким образом, решениеуравнения x2+D0x2+D0 получаем путём решения линейного уравненияukx±tkukx±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).