Алгоритм Берлекэмпа — Рабина

Алгоритм Берлекэмпа — Рабина (также метод Берлекэмпа) — вероятностный метод нахождения корней многочленов над полем ${\mathbb{F}}_p$$\mathbb {F} _{p}$с полиномиальной сложностью. Метод был описан американским математиком Элвином Берлекэмпом в 1970 году в качестве побочного к алгоритму факторизации многочленов над конечными полями и позже (в 1979 году) был доработан Михаэлем Рабином для случая произвольных конечных полей. Изначальная версия алгоритма, предложенная Берлекэмпом в 1967 году, не была полиномиальной. Опубликованная в 1970 году на основе результатов Цассенхауза^[en] версия алгоритма работала с большими значениями $p$$p$, в ней заглавный метод использовался в качестве вспомогательного. На момент публикации метод был распространён в профессиональной среде, однако редко встречался в литературе.

Элвин Берлекэмп

ИсторияПравить

 

Михаэль Ошер Рабин

Метод был предложен Элвином Берлекэмпом в его работе по факторизации многочленов над конечными полями. В ней факторизация многочлена на неприводимые сомножители над полем ${\mathbb{F}}_{p^k}$${\mathbb F}_{{p^{k}}}$  сводится к нахождению корней некоторых других многочленов над полем ${\mathbb{F}}_p$$\mathbb {F} _{p}$ . При этом в оригинальной работе отсутствовало доказательство корректности алгоритма. Алгоритм был доработан и обобщён на случай произвольных конечных полей Михаэлем Рабином. В 1986 году Рене Перальта описал похожий алгоритм, решающий задачу нахождения квадратного корня в поле ${\mathbb{F}}_p$$\mathbb {F} _{p}$ , а в 2000 году метод Перальты был обобщён для решения кубических уравнений.

В алгоритме Берлекэмпа многочлен $f(x)=a_0+a_{1}x+\cdots <!--\; \cdots \; -->+a_n{x}^n$$f(x)=a_{0}+a_{1}x+\dots +a_{n}x^{n}$  сперва представляется в виде произведения $f(x)=h_1(x)h_2(x)\dots <!--\; \dots \; -->h_n(x)$$f(x)=h_{1}(x)h_{2}(x)\dots h_{n}(x)$ , где $h_i$$h_{i}$  — произведение $r_i$$r_{i}$  многочленов степени $i$$i$ . Затем факторизация каждого такого многочлена $h_i(x)$$h_{i}(x)$  степени $i{r}_i$$ir_{i}$  сводится к поиску корней нового многочлена $H(x)$$H(x)$  степени $r_i$$r_{i}$ . В статье, вводящей алгоритм факторизации, было также предложено три метода для поиска корней многочлена в поле Галуа ${\mathbb{F}}_{p^k}$${\mathbb F}_{{p^{k}}}$ . Первые два сводят нахождение корней в поле ${\mathbb{F}}_{p^k}$${\mathbb F}_{{p^{k}}}$  к поиску корней в поле ${\mathbb{F}}_p$$\mathbb {F} _{p}$ . Третий метод, являющийся предметом данной статьи, решает задачу поиска корней в поле ${\mathbb{F}}_p$$\mathbb {F} _{p}$ , что вместе с двумя другими решает задачу факторизации.

Версия алгоритма факторизации, предложенная Берлекэмпом в его первой работе в 1967 г., работала за $O(n^3+prn)$$O(n^{3}+prn)$ , где $r$$r$  — количество неприводимых сомножителей многочлена. Таким образом, алгоритм являлся неполиномиальным и был непрактичным в случае, когда простое число $p$$p$  было достаточно большим. В 1969 г. эта проблема была решена Хансом Цассенхаузом^[en], показавшим, как свести узкое место алгоритма к задаче поиска корней некоторого многочлена. В 1970 г. статья Берлекэмпа была переиздана уже с учётом решений Цассенхауза.

В 1980 г. Михаэль Рабин провёл строгий анализ алгоритма, обобщил его для работы с конечным полями вида ${\mathbb{F}}_{p^k}$${\mathbb F}_{{p^{k}}}$  и доказал, что вероятность ошибки одной итерации алгоритма не превосходит $1/2$$1/2$ , а в 1981 г. Михаэль Бен-Ор усилил эту оценку до $1-<!--\; -\; -->1/2^{k-<!--\; -\; -->1}+O\left(1/\sqrt{p}\right)$${\textstyle 1-1/2^{k-1}+O\left(1/{\sqrt {p}}\right)}$ , где $k$$k$  — количество различных корней многочлена $f(x)$$f(x)$ . Вопрос существования полиномиального детерминированного алгоритма для нахождения корней многочлена над конечным полем остаётся открытым — основные алгоритмы факторизации многочленов, алгоритм Берлекэмпа и Алгоритм Кантора — Цассенхауза^[en] являются вероятностными. В 1981 году Поль Камьон^[fr] показал, что такой алгоритм существует для любого наперёд заданного числа $p$$p$ , однако этот результат исключительно теоретический и вопрос о возможности построения описанных им множеств на практике остаётся открытым.

В первом издании второго тома «Искусства программирования» про получисленные алгоритмы Дональд Кнут пишет, что аналогичные процедуры факторизации были известны к 1960 г., однако редко встречались в открытом доступе. Один из первых опубликованных примеров использования метода можно обнаружить в работе Голомба, Велша^[en] и Хейлса^[en] от 1959 года о факторизации трёхчленов над ${\mathbb{F}}_2$$\mathbb {F} _{2}$ , где рассматривался частный случай $p=2,z=1$$p=2,z=1$ .

АлгоритмПравить

Постановка задачиПравить

Пусть $p$$p$  — нечётное простое число. Рассмотрим многочлен $f(x)=a_0+a_{1}x+\cdots <!--\; \cdots \; -->+a_n{x}^n$${\textstyle f(x)=a_{0}+a_{1}x+\dots +a_{n}x^{n}}$  над полем ${\mathbb{Z}}_p$$\mathbb {Z} _{p}$  остатков по модулю $p$$p$ . Необходимо найти все числа ${\mathrm{\lambda <!--\; \lambda \; -->}}_1,\dots <!--\; \dots \; -->,{\mathrm{\lambda <!--\; \lambda \; -->}}_k$$\lambda _{1},\dots ,\lambda _{k}$  такие что $f({\mathrm{\lambda <!--\; \lambda \; -->}}_i)\equiv <!--\; \equiv \; -->0(\mathrm{mod}p)$${\textstyle f(\lambda _{i})\equiv 0{\pmod {p}}}$  для всех возможных $i$$i$ .

РандомизацияПравить

Пусть $f(x)=(x-<!--\; -\; -->{\mathrm{\lambda <!--\; \lambda \; -->}}_1)(x-<!--\; -\; -->{\mathrm{\lambda <!--\; \lambda \; -->}}_2)\dots <!--\; \dots \; -->(x-<!--\; -\; -->{\mathrm{\lambda <!--\; \lambda \; -->}}_n)$${\textstyle f(x)=(x-\lambda _{1})(x-\lambda _{2})\dots (x-\lambda _{n})}$ . Нахождение всех корней такого многочлена равносильно его разбиению на линейные множители. Чтобы найти такое разбиение, достаточно научиться разбивать многочлен на любые два множителя, а затем запускаться в них рекурсивно. Для этого вводится в рассмотрение многочлен $f_z(x)=f(x-<!--\; -\; -->z)=(x-<!--\; -\; -->{\mathrm{\lambda <!--\; \lambda \; -->}}_1-<!--\; -\; -->z)(x-<!--\; -\; -->{\mathrm{\lambda <!--\; \lambda \; -->}}_2-<!--\; -\; -->z)\dots <!--\; \dots \; -->(x-<!--\; -\; -->{\mathrm{\lambda <!--\; \lambda \; -->}}_n-<!--\; -\; -->z)$${\textstyle f_{z}(x)=f(x-z)=(x-\lambda _{1}-z)(x-\lambda _{2}-z)\dots (x-\lambda _{n}-z)}$ , где $z$$z$  — случайное число из ${\mathbb{Z}}_p$$\mathbb {Z} _{p}$ . Если такой многочлен можно представить в виде произведения $f_z(x)=p_0(x)p_1(x)$$f_{z}(x)=p_{0}(x)p_{1}(x)$ , то в терминах исходного многочлена это значит, что $f(x)=p_0(x+z)p_1(x+z)$$f(x)=p_{0}(x+z)p_{1}(x+z)$ , что даёт разбиение на множители исходного многочлена $f(x)$$f(x)$ .

Классификация элементов ${\mathbb{F}}_p$$\mathbb {F} _{p}$ Править

По критерию Эйлера для любого монома $(x-<!--\; -\; -->\mathrm{\lambda <!--\; \lambda \; -->})$$(x-\lambda )$  выполнено ровно одно из следующих свойств:

1. Одночлен равен $x$$x$ , если $\mathrm{\lambda <!--\; \lambda \; -->}=0$$\lambda =0$ ,
2. Одночлен делит $g_0(x)=(x^{(p-<!--\; -\; -->1)/2}-<!--\; -\; -->1)$${\textstyle g_{0}(x)=(x^{(p-1)/2}-1)}$ , если $\mathrm{\lambda <!--\; \lambda \; -->}$$\lambda$  — квадратичный вычет по модулю $p$$p$ ,
3. Одночлен делит $g_1(x)=(x^{(p-<!--\; -\; -->1)/2}+1)$${\textstyle g_{1}(x)=(x^{(p-1)/2}+1)}$ , если $\mathrm{\lambda <!--\; \lambda \; -->}$$\lambda$  — квадратичный невычет по этому модулю.

Таким образом, если $f_z(x)$$f_{z}(x)$  не делится на $x$$x$ , что можно проверить отдельно, то $f_z(x)$$f_{z}(x)$  равно произведению наибольших общих делителей $gcd(f_z(x);g_0(x))$$\gcd(f_{z}(x);g_{0}(x))$  и $gcd(f_z(x);g_1(x))$$\gcd(f_{z}(x);g_{1}(x))$ .

Метод БерлекэмпаПравить

Написанное выше приводит к следующему алгоритму:

1. В явном виде вычисляются коэффициенты многочлена $f_z(x)=f(x-<!--\; -\; -->z)$$f_{z}(x)=f(x-z)$ ,
2. Вычисляются остатки от деления $x,x^2,x^{2^2},x^{2^3},x^{2^4},\dots <!--\; \dots \; -->,x^{2^{\lfloor <!--\; \lfloor \; -->{\log }_2<!--\; \; -->p\rfloor <!--\; \rfloor \; -->}}$${\textstyle x,x^{2},x^{2^{2}},x^{2^{3}},x^{2^{4}},\dots ,x^{2^{\lfloor \log _{2}p\rfloor }}}$  на $f_z(x)$$f_{z}(x)$  последовательным возведением в квадрат и взятием остатка от $f_z(x)$$f_{z}(x)$ ,
3. Двоичным возведением в степень вычисляется остаток от деления $x^{(p-<!--\; -\; -->1)/2}$${\textstyle x^{(p-1)/2}}$  на $f_z(x)$${\textstyle f_{z}(x)}$  с использованием посчитанных на прошлом шаге многочленов,
4. Если $x^{(p-<!--\; -\; -->1)/2}\not\equiv \pm <!--\; \pm \; -->1(\mathrm{mod}{f}_z(x))$${\textstyle x^{(p-1)/2}\not \equiv \pm 1{\pmod {f_{z}(x)}}}$ , то указанные выше $gcd$$\gcd$  дают нетривиальное разбиение $f_z(x)$$f_{z}(x)$  на множители,
5. В противном случае все корни $f_z(x)$$f_{z}(x)$  являются вычетами или невычетами одновременно и стоит попробовать другое значения $z$$z$ .

Если $f(x)$$f(x)$  также делится на некоторый многочлен $g(x)$$g(x)$ , не имеющий корней в ${\mathbb{Z}}_p$$\mathbb {Z} _{p}$ , то при подсчёте $gcd$$\gcd$  с $g_0(x)$$g_{0}(x)$  и $g_1(x)$$g_{1}(x)$  будет получено разбиение бесквадратного многочлена $f_z(x)/g_z(x)$$f_{z}(x)/g_{z}(x)$  на нетривиальные сомножители, поэтому алгоритм позволяет найти все корни любых многочленов над ${\mathbb{Z}}_p$$\mathbb {Z} _{p}$ , а не только тех, которые разбиваются в произведение мономов.

Извлечение квадратного корняПравить

Пусть нужно решить сравнение $x^2\equiv <!--\; \equiv \; -->a(\mathrm{mod}p)$${\textstyle x^{2}\equiv a{\pmod {p}}}$ , решениями которого являются элементы $\mathrm{\beta <!--\; \beta \; -->}$$\beta$  и $-<!--\; -\; -->\mathrm{\beta <!--\; \beta \; -->}$$-\beta$  соответственно. Их нахождение эквивалентно факторизации многочлена $f(x)=x^2-<!--\; -\; -->a=(x-<!--\; -\; -->\mathrm{\beta <!--\; \beta \; -->})(x+\mathrm{\beta <!--\; \beta \; -->})$${\textstyle f(x)=x^{2}-a=(x-\beta )(x+\beta )}$  над полем ${\mathbb{Z}}_p$$\mathbb {Z} _{p}$ . В таком частном случае задача упрощается, так как для решения достаточно посчитать только $gcd(f_z(x);g_0(x))$$\gcd(f_{z}(x);g_{0}(x))$ . Для полученного многочлена будет верно ровно одно из утверждений:

1. НОД равен $1$$1$ , из чего следует, что $z+\mathrm{\beta <!--\; \beta \; -->}$$z+\beta$  и $z-<!--\; -\; -->\mathrm{\beta <!--\; \beta \; -->}$$z-\beta$  являются квадратичными невычетами одновременно,
2. НОД равен $f_z(x)$$f_{z}(x)$ , из чего следует, что оба числа являются квадратичными вычетами,
3. НОД равен одночлену $(x-<!--\; -\; -->t)$$(x-t)$ , из чего следует, что ровно одно число из двух является квадратичным вычетом.

В третьем случае полученный одночлен должен быть равен или $(x-<!--\; -\; -->z-<!--\; -\; -->\mathrm{\beta <!--\; \beta \; -->})$$(x-z-\beta )$ , или $(x-<!--\; -\; -->z+\mathrm{\beta <!--\; \beta \; -->})$$(x-z+\beta )$ . Это позволяет записать решение в виде $\mathrm{\beta <!--\; \beta \; -->}=(t-<!--\; -\; -->z)(\mathrm{mod}p)$${\textstyle \beta =(t-z){\pmod {p}}}$ .

ПримерПравить

Пусть нужно решить сравнение $x^2\equiv <!--\; \equiv \; -->5(\mathrm{mod}11)$${\textstyle x^{2}\equiv 5{\pmod {11}}}$ . Для этого нужно факторизовать $f(x)=x^2-<!--\; -\; -->5=(x-<!--\; -\; -->\mathrm{\beta <!--\; \beta \; -->})(x+\mathrm{\beta <!--\; \beta \; -->})$$f(x)=x^{2}-5=(x-\beta )(x+\beta )$ . Рассмотрим возможные значения $z$$z$ :

1. Пусть $z=3$$z=3$ . Тогда $f_z(x)=(x-<!--\; -\; -->3{)}^2-<!--\; -\; -->5=x^2-<!--\; -\; -->6x+4$$f_{z}(x)=(x-3)^{2}-5=x^{2}-6x+4$ , откуда $gcd(x^2-<!--\; -\; -->6x+4;x^5-<!--\; -\; -->1)=1$$\gcd(x^{2}-6x+4;x^{5}-1)=1$ . Оба числа $3\pm <!--\; \pm \; -->\mathrm{\beta <!--\; \beta \; -->}$$3\pm \beta$  являются невычетами и нужно брать другое $z$$z$ .

1. Пусть $z=2$$z=2$ . Тогда $f_z(x)=(x-<!--\; -\; -->2{)}^2-<!--\; -\; -->5=x^2-<!--\; -\; -->4x-<!--\; -\; -->1$$f_{z}(x)=(x-2)^{2}-5=x^{2}-4x-1$ , откуда $gcd(x^2-<!--\; -\; -->4x-<!--\; -\; -->1;x^5-<!--\; -\; -->1)\equiv <!--\; \equiv \; -->x-<!--\; -\; -->9(\mathrm{mod}11)$${\textstyle \gcd(x^{2}-4x-1;x^{5}-1)\equiv x-9{\pmod {11}}}$ . Отсюда $x-<!--\; -\; -->9=x-<!--\; -\; -->2-<!--\; -\; -->\mathrm{\beta <!--\; \beta \; -->}$${\textstyle x-9=x-2-\beta }$ , значит $\mathrm{\beta <!--\; \beta \; -->}\equiv <!--\; \equiv \; -->7(\mathrm{mod}11)$$\beta \equiv 7{\pmod {11}}$  и $-<!--\; -\; -->\mathrm{\beta <!--\; \beta \; -->}\equiv <!--\; \equiv \; -->-<!--\; -\; -->7\equiv <!--\; \equiv \; -->4(\mathrm{mod}11)$${\textstyle -\beta \equiv -7\equiv 4{\pmod {11}}}$ .

Проверка показывает, что действительно $7^2\equiv <!--\; \equiv \; -->49\equiv <!--\; \equiv \; -->5(\mathrm{mod}11)$${\textstyle 7^{2}\equiv 49\equiv 5{\pmod {11}}}$  и $4^2\equiv <!--\; \equiv \; -->16\equiv <!--\; \equiv \; -->5(\mathrm{mod}11)$${\textstyle 4^{2}\equiv 16\equiv 5{\pmod {11}}}$ .

Обоснование методаПравить

Алгоритм находит разбиение $f_z(x)$$f_{z}(x)$  на нетривиальные множители во всех случаях, за исключением тех, в которых все числа $z+{\mathrm{\lambda <!--\; \lambda \; -->}}_1,z+{\mathrm{\lambda <!--\; \lambda \; -->}}_2,\dots <!--\; \dots \; -->,z+{\mathrm{\lambda <!--\; \lambda \; -->}}_n$$z+\lambda _{1},z+\lambda _{2},\dots ,z+\lambda _{n}$  являются вычетами или невычетами одновременно. Согласно теории циклотомии, вероятность такого события для случая, когда ${\mathrm{\lambda <!--\; \lambda \; -->}}_1,\dots <!--\; \dots \; -->,{\mathrm{\lambda <!--\; \lambda \; -->}}_n$$\lambda _{1},\dots ,\lambda _{n}$  сами одновременно являются вычетами или невычетами одновременно (то есть, когда $z=0$$z=0$  не подходит для нашей процедуры), можно оценить как $1/2^{k-<!--\; -\; -->1}$$1/2^{k-1}$ , где $k$$k$  — количество различных чисел среди ${\mathrm{\lambda <!--\; \lambda \; -->}}_1,\dots <!--\; \dots \; -->,{\mathrm{\lambda <!--\; \lambda \; -->}}_n$$\lambda _{1},\dots ,\lambda _{n}$ . Таким образом, вероятность ошибки алгоритма не превосходит $1/2$$1/2$ .

Применение к факторизации многочленовПравить

Основная статья: Алгоритм Берлекэмпа

Из теории конечных полей известно, что если степень неприводимого многочлена $q(x)$$q(x)$  равна $d$$d$ , то такой многочлен является делителем $x^{p^d}-<!--\; -\; -->x$$x^{p^{d}}-x$  и не является делителем $x^{p^t}-<!--\; -\; -->x$$x^{p^{t}}-x$  для $t<d$ .

Таким образом, последовательно рассматривая многочлены $h_i(x)=gcd(f_i(x),x^{p^i}-<!--\; -\; -->1)$$h_{i}(x)=\gcd(f_{i}(x),x^{p^{i}}-1)$  где $f_1(x)=f(x)$$f_{1}(x)=f(x)$  и $f_i(x)=f_{i-<!--\; -\; -->1}(x)/h_{i-<!--\; -\; -->1}(x)$$f_{i}(x)=f_{i-1}(x)/h_{i-1}(x)$  для $i>1$$i>1$ , можно разбить многочлен $f(x)$$f(x)$  на множители вида $f(x)=h_1(x)\dots <!--\; \dots \; -->h_n(x)$$f(x)=h_{1}(x)\dots h_{n}(x)$ , где $h_i(x)$$h_{i}(x)$  — это произведение всех неприводимых многочленов степени $i$$i$ , которые делят многочлен $f(x)$$f(x)$ . Зная степень $h_i(x)$$h_{i}(x)$ , можно определить количество таких многочленов, равное $r_i=\mathrm{deg}<!--\; \; -->h_i(x)/i$$r_{i}=\deg h_{i}(x)/i$ . Пусть $h_i(x)=p_1(x)\dots <!--\; \dots \; -->p_{r_i}(x)$$h_{i}(x)=p_{1}(x)\dots p_{r_{i}}(x)$ . Если рассмотреть многочлен $p_j(x-<!--\; -\; -->z)$$p_{j}(x-z)$ , где $z\in <!--\; \in \; -->{\mathbb{F}}_p$${\textstyle z\in \mathbb {F} _{p}}$ , то порядок такого многочлена $d_j$$d_{j}$  в поле ${\mathbb{F}}_{p^i}$${\textstyle \mathbb {F} _{p^{i}}}$  должен делить число $p^i-<!--\; -\; -->1$$p^{i}-1$ . Если $d_j$$d_{j}$  не делится на $d_k$$d_{k}$ , то многочлен $x^{d_j}-<!--\; -\; -->x$${\textstyle x^{d_{j}}-x}$  делится на $p_j(x-<!--\; -\; -->z)$${\textstyle p_{j}(x-z)}$ , но не на $p_k(x-<!--\; -\; -->z)$${\textstyle p_{k}(x-z)}$ .

Исходя из этого Цассенхауз^[en] предложил искать делители многочлена $h_i(x-<!--\; -\; -->z)$$h_{i}(x-z)$  в виде $gcd(h_i(x-<!--\; -\; -->z),x^f-<!--\; -\; -->1)$${\textstyle \gcd(h_{i}(x-z),x^{f}-1)}$ , где $f$$f$  — некоторый достаточно большой делитель $p^i-<!--\; -\; -->1$$p^{i}-1$ , например, $f=\frac{p^i-<!--\; -\; -->1}{2}$${\textstyle f={\frac {p^{i}-1}{2}}}$ . В частном случае $i=1$$i=1$  получается в точности метод Берлекэмпа как он описан выше.

Время работыПравить

Поэтапно время работы одной итерации алгоритма можно оценить следующим образом, считая степень многочлена равной $n$$n$ :

1. Учитывая, что $(x-<!--\; -\; -->z{)}^k=\underset{i=0}{\overset{k}{\sum <!--\; \sum \; -->}}(\genfrac{}{}{0ex}{}{k}{i})(-<!--\; -\; -->z{)}^{k-<!--\; -\; -->i}{x}^i$${\textstyle (x-z)^{k}=\sum \limits _{i=0}^{k}{\binom {k}{i}}(-z)^{k-i}x^{i}}$  по формуле бинома Ньютона, переход от $f(x)$$f(x)$  к $f(x-<!--\; -\; -->z)$$f(x-z)$  делается за $O(n^2)$$O(n^{2})$ ,
2. Произведение многочленов и взятие остатка от одного многочлена по модулю другого делается за $O(n^2)$${\textstyle O(n^{2})}$ , поэтому вычисление $x^{2^k}{modf}_z(x)$${\textstyle x^{2^{k}}{\bmod {f}}_{z}(x)}$  делается за $O(n^2\log <!--\; \; -->p)$${\textstyle O(n^{2}\log p)}$ ,
3. Аналогично предыдущему пункту, двоичное возведение в степень делается за $O(n^2\log <!--\; \; -->p)$$O(n^{2}\log p)$ ,
4. Взятие $gcd$$\gcd$  от двух многочленов по алгоритму Евклида делается за $O(n^2)$$O(n^{2})$ .

Таким образом, одна итерация алгоритма может быть произведена за $O(n^2\log <!--\; \; -->p)$$O(n^{2}\log p)$  арифметических операций с элементами ${\mathbb{F}}_p$$\mathbb {F} _{p}$ , а нахождение всех корней многочлена требует в среднем $O(n^2\log <!--\; \; -->n\log <!--\; \; -->p)$$O(n^{2}\log n\log p)$ . В частном случае извлечения квадратного корня величина $n$$n$  равна двум, поэтому время работы оценивается как $O(\log <!--\; \; -->p)$$O(\log p)$  на одну итерацию алгоритма.