Русская Википедия:Алгоритм Поклингтона

Содержание

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

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

<math>x^2 \equiv a \pmod p, \, </math>

где x и a — целые числа и a является квадратичным вычетом.

Алгоритм является одним из первых эффективных методов решения такого уравнения. Алгоритм описал Шаблон:Не переведено 5 в 1917 годуШаблон:Sfn.

Алгоритм

(Замечание: Все знаки <math>\equiv</math> означают <math>\pmod p</math>, если не сказано другое.)

Вход:

• p, нечётное простое число
• a, целое число, являющееся двоичным вычетом <math>\pmod p</math>.

Выход:

• x, целое число, удовлетворяющее тождеству <math>x^2 \equiv a</math>. Заметим, что если x является решением, то −x также является решением и, поскольку p нечётно, <math>x \neq -x</math>. Таким образом, всегда существует второе решение, если хотя бы одно найдено.

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

Поклингтон рассматривает 3 различных случая для p:

Первый случай, если <math>p=4m+3</math>, с <math>m \in \mathbb{N}</math>, решение равно <math>x \equiv \pm a^{m+1}</math>.

Второй случай, если <math>p=8m+5</math>, с <math>m \in \mathbb{N}</math> и

1. <math>a^{2m+1} \equiv 1</math>, решение равно <math>x \equiv \pm a^{m+1}</math>.
2. <math>a^{2m+1} \equiv -1</math>, 2 не является (квадратичным) вычетом, так что <math>4^{2m+1} \equiv -1</math>. Это означает, что <math>(4a)^{2m+1} \equiv 1</math>, так что <math>y \equiv \pm (4a)^{m+1}</math> является решением <math>y^2 \equiv 4a</math>. Следовательно, <math>x \equiv \pm y/2</math> или, если y нечётно, <math>x \equiv \pm (p+y)/2</math>.

Третий случай, если <math>p=8m+1</math>, положим <math>D \equiv -a</math>, так что уравнение превращается в <math>x^2 + D \equiv 0</math>. Теперь методом проб и ошибок находим <math>t_1</math> и <math>u_1</math>, такие, что <math>N = t_1^2 - D u_1^2</math> не является квадратичным вычетом. Далее пусть

<math>t_n = \frac{(t_1 + u_1 \sqrt{D})^n + (t_1 - u_1 \sqrt{D})^n}{2}</math>

<math>u_n = \frac{(t_1 + u_1 \sqrt{D})^n - (t_1 - u_1 \sqrt{D})^n}{2 \sqrt{D}}</math>.

Теперь выполняются следующие равенства:

<math>t_{m+n} = t_m t_n + D u_m u_n</math>

<math>u_{m+n} = t_m u_n + t_n u_m</math>

<math>t_n^2 - D u_n^2 = N^n</math>.

Если p имеет вид <math>4m+1</math> (что верно, если p имеет вид <math>8m+1</math>), D является квадратичным вычетом и <math>t_p \equiv t_1^p \equiv t_1, \quad u_p \equiv u_1^p D^{(p-1)/2} \equiv u_1</math>. Теперь равенства

<math>t_1 \equiv t_{p-1} t_1 + D u_{p-1} u_1</math>

<math>u_1 \equiv t_{p-1} u_1 + t_1 u_{p-1}</math>

дают решение <math>t_{p-1} \equiv 1, \quad u_{p-1} \equiv 0</math>.

Пусть <math>p-1 = 2r</math>. Тогда <math>0 \equiv u_{p-1} \equiv 2 t_r u_r</math>. Это означает, что либо <math>t_r</math>, либо <math>u_r</math> делятся на p. Если делится <math>u_r</math>, положим <math>r=2s</math> и проводим аналогичные выкладки с <math>0 \equiv 2 t_s u_s</math>. Не все <math>u_i</math> делятся на p, так, <math>u_1</math> не делится. Случай <math>u_m \equiv 0</math> с нечётным m невозможен, поскольку выполняется <math>t_m^2 - D u_m^2 \equiv N^m</math> и это должно означать, что <math>t_m^2</math> конгруэнтно квадратичному невычету, получили противоречие. Таким образом, цикла прерывается, когда <math>t_l \equiv 0</math> для некоторого l. Это даёт <math>-D u_l^2 \equiv N^l</math>, а поскольку <math>-D</math> является квадратичным вычетом, l должно быть чётным. Положим <math>l = 2k</math>. Тогда <math>0 \equiv t_l \equiv t_k^2 + D u_k^2</math>. Таким образом, решение уравнения <math>x^2 + D \equiv 0</math> получаем путём решения линейного уравнения <math>u_k x \equiv \pm t_k</math>.

Примеры

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

Пример 1

Решаем конгруэнтное уравнение

<math>x^2 \equiv 18 \pmod {23}.</math>

Модуль равен 23. Поскольку <math>23 = 4 \cdot 5 + 3</math>, <math>m=5</math>. Решениями должны быть значения <math>x \equiv \pm 18^6 \equiv \pm 8\pmod {23}</math>, и это действительно решения: <math>(\pm 8)^2 \equiv 64 \equiv 18\pmod {23}</math>.

Пример 2

Решаем конгруэнтное уравнение

<math>x^2 \equiv 10 \pmod{13}.</math>

Модуль равен 13. Поскольку <math>13 = 8 \cdot 1 + 5</math>, <math>m=1</math>. Проверяем, что <math>10^{2m+1} \equiv 10^3 \equiv -1\pmod{13}</math>. Таким образом, решением будет <math>x \equiv \pm y/2 \equiv \pm (4a)^{2}/2 \equiv \pm 800 \equiv \pm 7\pmod{13}</math>. И это действительно решения: <math>(\pm 7)^2 \equiv 49 \equiv 10\pmod{13}</math>.

Пример 3

Решаем конгруэнтное уравнение <math>x^2 \equiv 13 \pmod {17}</math>. Запишем уравнение в виде <math>x^2 -13 =0</math>. Сначала найдём <math>t_1</math> и <math>u_1</math>, такие, что <math>t_1^2 + 13u_1^2</math> является квадратичным невычетом. Возьмён, например, <math>t_1=3, u_1 = 1</math>. Найдём <math>t_8</math>, <math>u_8</math>, начав с

<math>t_2 = t_1 t_1 + 13u_1u_1 = 9-13 = -4 \equiv 13\pmod {17},\,</math>,

<math>u_2 = t_1u_1 + t_1u_1 = 3+3 \equiv 6\pmod {17}.\,</math>

Продолжим аналогично <math>t_4 = -299 \equiv 7 \pmod {17}\, u_4=156 \equiv 3\pmod {17}</math>, <math>t_8=-68 \equiv 0\pmod {17}\, u_8 = 42 \equiv 8\pmod {17}.</math>

Поскольку <math>t_8 = 0</math>, получаем <math> 0 \equiv t_4^2 + 13u_4^2 \equiv 7^2 - 13 \cdot 3^2\pmod {17}</math>, что ведёт к уравнению <math>3x \equiv \pm 7\pmod {17}</math>. Последнее имеет решения <math>x \equiv \pm 8\pmod {17}</math>. Действительно, <math>(\pm 8)^2 = 64 \equiv 13\pmod {17}</math>.

Литература

• Шаблон:Статья