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

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

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

История

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

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

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

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

В 1980 г. Михаэль Рабин провёл строгий анализ алгоритма, обобщил его для работы с конечным полями вида ${𝔽}_{p^k}$ и доказал, что вероятность ошибки одной итерации алгоритма не превосходит $1/2$, а в 1981 г. Михаэль Бен-Ор усилил эту оценку до $1-1/2^{k-1}+O(1/\sqrt{p})$, где $k$ — количество различных корней многочлена $f(x)$. Вопрос существования полиномиального детерминированного алгоритма для нахождения корней многочлена над конечным полем остаётся открытым — основные алгоритмы факторизации многочленов, алгоритм Берлекэмпа и Шаблон:Не переведено 5 являются вероятностными. В 1981 году Шаблон:Не переведено 5 показал, что такой алгоритм существует для любого наперёд заданного числа $p$, однако этот результат исключительно теоретический и вопрос о возможности построения описанных им множеств на практике остаётся открытым.

В первом издании второго тома «Искусства программирования» про получисленные алгоритмы Дональд Кнут пишет, что аналогичные процедуры факторизации были известны к 1960 г., однако редко встречались в открытом доступе. Один из первых опубликованных примеров использования метода можно обнаружить в работе Голомба, Шаблон:Не переведено 5 и Шаблон:Не переведено 5 от 1959 года о факторизации трёхчленов над ${𝔽}_2$, где рассматривался частный случай $p=2,z=1$.

Алгоритм

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

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

Рандомизация

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

Классификация элементов ${𝔽}_p$

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

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

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

Метод Берлекэмпа

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

1. В явном виде вычисляются коэффициенты многочлена $f_z(x)=f(x-z)$,
2. Вычисляются остатки от деления $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)$,
3. Двоичным возведением в степень вычисляется остаток от деления $x^{(p-1)/2}$ на $f_z(x)$ с использованием посчитанных на прошлом шаге многочленов,
4. Если $x^{(p-1)/2}\equiv ̸\pm 1(\mathrm{mod}{f}_z(x))$, то указанные выше $\gcd$ дают нетривиальное разбиение $f_z(x)$ на множители,
5. В противном случае все корни $f_z(x)$ являются вычетами или невычетами одновременно и стоит попробовать другое значения $z$.

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

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

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

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

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

Пример

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

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

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

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

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

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

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

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

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

Исходя из этого Шаблон:Не переведено 5 предложил искать делители многочлена $h_i(x-z)$ в виде $\gcd (h_i(x-z),x^f-1)$, где $f$ — некоторый достаточно большой делитель $p^i-1$, например, $f=\frac{p^i-1}{2}$. В частном случае $i=1$ получается в точности метод Берлекэмпа как он описан выше.

Время работы

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

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

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