Алгоритм Поклингтона — это техника решения конгруэнтного уравнения вида
x
2
≡
a
(
mod
p
)
,
{\displaystyle x^{2}\equiv a{\pmod {p}},\,}
где x и a — целые числа и a является квадратичным вычетом .
Алгоритм является одним из первых эффективных методов решения такого уравнения. Алгоритм описал Г.К. Поклингтон [англ.] в 1917 году[ 1] .
(Замечание : Все знаки
≡
{\displaystyle \equiv }
означают
(
mod
p
)
{\displaystyle {\pmod {p}}}
, если не сказано другое.)
Вход:
p , нечётное простое число
a , целое число, являющееся двоичным вычетом
(
mod
p
)
{\displaystyle {\pmod {p}}}
.
Выход:
x , целое число, удовлетворяющее тождеству
x
2
≡
a
{\displaystyle x^{2}\equiv a}
. Заметим, что если x является решением, то −x также является решением и, поскольку p нечётно,
x
≠
−
x
{\displaystyle x\neq -x}
. Таким образом, всегда существует второе решение, если хотя бы одно найдено.
Поклингтон рассматривает 3 различных случая для p :
Первый случай, если
p
=
4
m
+
3
{\displaystyle p=4m+3}
, с
m
∈
N
{\displaystyle m\in \mathbb {N} }
, решение равно
x
≡
±
a
m
+
1
{\displaystyle x\equiv \pm a^{m+1}}
.
Второй случай, если
p
=
8
m
+
5
{\displaystyle p=8m+5}
, с
m
∈
N
{\displaystyle m\in \mathbb {N} }
и
a
2
m
+
1
≡
1
{\displaystyle a^{2m+1}\equiv 1}
, решение равно
x
≡
±
a
m
+
1
{\displaystyle x\equiv \pm a^{m+1}}
.
a
2
m
+
1
≡
−
1
{\displaystyle a^{2m+1}\equiv -1}
, 2 не является (квадратичным) вычетом, так что
4
2
m
+
1
≡
−
1
{\displaystyle 4^{2m+1}\equiv -1}
. Это означает, что
(
4
a
)
2
m
+
1
≡
1
{\displaystyle (4a)^{2m+1}\equiv 1}
, так что
y
≡
±
(
4
a
)
m
+
1
{\displaystyle y\equiv \pm (4a)^{m+1}}
является решением
y
2
≡
4
a
{\displaystyle y^{2}\equiv 4a}
. Следовательно,
x
≡
±
y
/
2
{\displaystyle x\equiv \pm y/2}
или, если y нечётно,
x
≡
±
(
p
+
y
)
/
2
{\displaystyle x\equiv \pm (p+y)/2}
.
Третий случай, если
p
=
8
m
+
1
{\displaystyle p=8m+1}
, положим
D
≡
−
a
{\displaystyle D\equiv -a}
, так что уравнение превращается в
x
2
+
D
≡
0
{\displaystyle x^{2}+D\equiv 0}
. Теперь методом проб и ошибок находим
t
1
{\displaystyle t_{1}}
и
u
1
{\displaystyle u_{1}}
, такие, что
N
=
t
1
2
−
D
u
1
2
{\displaystyle N=t_{1}^{2}-Du_{1}^{2}}
не является квадратичным вычетом. Далее пусть
t
n
=
(
t
1
+
u
1
D
)
n
+
(
t
1
−
u
1
D
)
n
2
{\displaystyle t_{n}={\frac {(t_{1}+u_{1}{\sqrt {D}})^{n}+(t_{1}-u_{1}{\sqrt {D}})^{n}}{2}}}
u
n
=
(
t
1
+
u
1
D
)
n
−
(
t
1
−
u
1
D
)
n
2
D
{\displaystyle u_{n}={\frac {(t_{1}+u_{1}{\sqrt {D}})^{n}-(t_{1}-u_{1}{\sqrt {D}})^{n}}{2{\sqrt {D}}}}}
.
Теперь выполняются следующие равенства:
t
m
+
n
=
t
m
t
n
+
D
u
m
u
n
{\displaystyle t_{m+n}=t_{m}t_{n}+Du_{m}u_{n}}
u
m
+
n
=
t
m
u
n
+
t
n
u
m
{\displaystyle u_{m+n}=t_{m}u_{n}+t_{n}u_{m}}
t
n
2
−
D
u
n
2
=
N
n
{\displaystyle t_{n}^{2}-Du_{n}^{2}=N^{n}}
.
Если p имеет вид
4
m
+
1
{\displaystyle 4m+1}
(что верно, если p имеет вид
8
m
+
1
{\displaystyle 8m+1}
), D является квадратичным вычетом и
t
p
≡
t
1
p
≡
t
1
,
u
p
≡
u
1
p
D
(
p
−
1
)
/
2
≡
u
1
{\displaystyle t_{p}\equiv t_{1}^{p}\equiv t_{1},\quad u_{p}\equiv u_{1}^{p}D^{(p-1)/2}\equiv u_{1}}
. Теперь равенства
t
1
≡
t
p
−
1
t
1
+
D
u
p
−
1
u
1
{\displaystyle t_{1}\equiv t_{p-1}t_{1}+Du_{p-1}u_{1}}
u
1
≡
t
p
−
1
u
1
+
t
1
u
p
−
1
{\displaystyle u_{1}\equiv t_{p-1}u_{1}+t_{1}u_{p-1}}
дают решение
t
p
−
1
≡
1
,
u
p
−
1
≡
0
{\displaystyle t_{p-1}\equiv 1,\quad u_{p-1}\equiv 0}
.
Пусть
p
−
1
=
2
r
{\displaystyle p-1=2r}
. Тогда
0
≡
u
p
−
1
≡
2
t
r
u
r
{\displaystyle 0\equiv u_{p-1}\equiv 2t_{r}u_{r}}
. Это означает, что либо
t
r
{\displaystyle t_{r}}
, либо
u
r
{\displaystyle u_{r}}
делятся на p . Если делится
u
r
{\displaystyle u_{r}}
, положим
r
=
2
s
{\displaystyle r=2s}
и проводим аналогичные выкладки с
0
≡
2
t
s
u
s
{\displaystyle 0\equiv 2t_{s}u_{s}}
. Не все
u
i
{\displaystyle u_{i}}
делятся на p , так,
u
1
{\displaystyle u_{1}}
не делится. Случай
u
m
≡
0
{\displaystyle u_{m}\equiv 0}
с нечётным m невозможен, поскольку выполняется
t
m
2
−
D
u
m
2
≡
N
m
{\displaystyle t_{m}^{2}-Du_{m}^{2}\equiv N^{m}}
и это должно означать, что
t
m
2
{\displaystyle t_{m}^{2}}
конгруэнтно квадратичному невычету, получили противоречие. Таким образом, цикла прерывается, когда
t
l
≡
0
{\displaystyle t_{l}\equiv 0}
для некоторого l . Это даёт
−
D
u
l
2
≡
N
l
{\displaystyle -Du_{l}^{2}\equiv N^{l}}
, а поскольку
−
D
{\displaystyle -D}
является квадратичным вычетом, l должно быть чётным. Положим
l
=
2
k
{\displaystyle l=2k}
. Тогда
0
≡
t
l
≡
t
k
2
+
D
u
k
2
{\displaystyle 0\equiv t_{l}\equiv t_{k}^{2}+Du_{k}^{2}}
. Таким образом, решение уравнения
x
2
+
D
≡
0
{\displaystyle x^{2}+D\equiv 0}
получаем путём решения линейного уравнения
u
k
x
≡
±
t
k
{\displaystyle u_{k}x\equiv \pm t_{k}}
.
Ниже приведены 3 примера, соответствующие 3 различным случаям. В примерах все знаки
≡
{\displaystyle \equiv }
означает сравнение по модулю .
Решаем конгруэнтное уравнение
x
2
≡
18
(
mod
23
)
.
{\displaystyle x^{2}\equiv 18{\pmod {23}}.}
Модуль равен 23. Поскольку
23
=
4
⋅
5
+
3
{\displaystyle 23=4\cdot 5+3}
,
m
=
5
{\displaystyle m=5}
.
Решениями должны быть значения
x
≡
±
18
6
≡
±
8
(
mod
23
)
{\displaystyle x\equiv \pm 18^{6}\equiv \pm 8{\pmod {23}}}
, и это действительно решения:
(
±
8
)
2
≡
64
≡
18
(
mod
23
)
{\displaystyle (\pm 8)^{2}\equiv 64\equiv 18{\pmod {23}}}
.
Решаем конгруэнтное уравнение
x
2
≡
10
(
mod
13
)
.
{\displaystyle x^{2}\equiv 10{\pmod {13}}.}
Модуль равен 13. Поскольку
13
=
8
⋅
1
+
5
{\displaystyle 13=8\cdot 1+5}
,
m
=
1
{\displaystyle m=1}
. Проверяем, что
10
2
m
+
1
≡
10
3
≡
−
1
(
mod
13
)
{\displaystyle 10^{2m+1}\equiv 10^{3}\equiv -1{\pmod {13}}}
. Таким образом, решением будет
x
≡
±
y
/
2
≡
±
(
4
a
)
2
/
2
≡
±
800
≡
±
7
(
mod
13
)
{\displaystyle x\equiv \pm y/2\equiv \pm (4a)^{2}/2\equiv \pm 800\equiv \pm 7{\pmod {13}}}
. И это действительно решения:
(
±
7
)
2
≡
49
≡
10
(
mod
13
)
{\displaystyle (\pm 7)^{2}\equiv 49\equiv 10{\pmod {13}}}
.
Решаем конгруэнтное уравнение
x
2
≡
13
(
mod
17
)
{\displaystyle x^{2}\equiv 13{\pmod {17}}}
. Запишем уравнение в виде
x
2
−
13
=
0
{\displaystyle x^{2}-13=0}
. Сначала найдём
t
1
{\displaystyle t_{1}}
и
u
1
{\displaystyle u_{1}}
, такие, что
t
1
2
+
13
u
1
2
{\displaystyle t_{1}^{2}+13u_{1}^{2}}
является квадратичным невычетом. Возьмён, например,
t
1
=
3
,
u
1
=
1
{\displaystyle t_{1}=3,u_{1}=1}
. Найдём
t
8
{\displaystyle t_{8}}
,
u
8
{\displaystyle u_{8}}
, начав с
t
2
=
t
1
t
1
+
13
u
1
u
1
=
9
−
13
=
−
4
≡
13
(
mod
17
)
,
{\displaystyle t_{2}=t_{1}t_{1}+13u_{1}u_{1}=9-13=-4\equiv 13{\pmod {17}},\,}
,
u
2
=
t
1
u
1
+
t
1
u
1
=
3
+
3
≡
6
(
mod
17
)
.
{\displaystyle u_{2}=t_{1}u_{1}+t_{1}u_{1}=3+3\equiv 6{\pmod {17}}.\,}
Продолжим аналогично
t
4
=
−
299
≡
7
(
mod
17
)
u
4
=
156
≡
3
(
mod
17
)
{\displaystyle t_{4}=-299\equiv 7{\pmod {17}}\,u_{4}=156\equiv 3{\pmod {17}}}
,
t
8
=
−
68
≡
0
(
mod
17
)
u
8
=
42
≡
8
(
mod
17
)
.
{\displaystyle t_{8}=-68\equiv 0{\pmod {17}}\,u_{8}=42\equiv 8{\pmod {17}}.}
Поскольку
t
8
=
0
{\displaystyle t_{8}=0}
, получаем
0
≡
t
4
2
+
13
u
4
2
≡
7
2
−
13
⋅
3
2
(
mod
17
)
{\displaystyle 0\equiv t_{4}^{2}+13u_{4}^{2}\equiv 7^{2}-13\cdot 3^{2}{\pmod {17}}}
, что ведёт к уравнению
3
x
≡
±
7
(
mod
17
)
{\displaystyle 3x\equiv \pm 7{\pmod {17}}}
. Последнее имеет решения
x
≡
±
8
(
mod
17
)
{\displaystyle x\equiv \pm 8{\pmod {17}}}
. Действительно,
(
±
8
)
2
=
64
≡
13
(
mod
17
)
{\displaystyle (\pm 8)^{2}=64\equiv 13{\pmod {17}}}
.
H.C. Pocklington. Тhe direct solution of the quadratic and cubic binomial congruences with prime moduli // Proceedings of the Cambridge Philosophical Society. — 1917. — Т. 19 .