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

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

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

В алгоритме Берлекэмпа многочлен ${\displaystyle f(x)=a_{0}+a_{1}x+\dots +a_{n}x^{n}}$ сперва представляется в виде произведения ${\displaystyle f(x)=h_{1}(x)h_{2}(x)\dots h_{n}(x)}$, где ${\displaystyle h_{i}}$ — произведение ${\displaystyle r_{i}}$ многочленов степени ${\displaystyle i}$. Затем факторизация каждого такого многочлена ${\displaystyle h_{i}(x)}$ степени ${\displaystyle ir_{i}}$ сводится к поиску корней нового многочлена ${\displaystyle H(x)}$ степени ${\displaystyle r_{i}}$. В статье, вводящей алгоритм факторизации, было также предложено три метода для поиска корней многочлена в поле Галуа ${\displaystyle \mathbb {F} _{p^{k}}}$. Первые два сводят нахождение корней в поле ${\displaystyle \mathbb {F} _{p^{k}}}$ к поиску корней в поле ${\displaystyle \mathbb {F} _{p}}$. Третий метод, являющийся предметом данной статьи, решает задачу поиска корней в поле ${\displaystyle \mathbb {F} _{p}}$, что вместе с двумя другими решает задачу факторизации[1].

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

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

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

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

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

Таким образом, последовательно рассматривая многочлены ${\displaystyle h_{i}(x)=\gcd(f_{i}(x),x^{p^{i}}-1)}$ где ${\displaystyle f_{1}(x)=f(x)}$ и ${\displaystyle f_{i}(x)=f_{i-1}(x)/h_{i-1}(x)}$ для ${\displaystyle i>1}$, можно разбить многочлен ${\displaystyle f(x)}$ на множители вида ${\displaystyle f(x)=h_{1}(x)\dots h_{n}(x)}$, где ${\displaystyle h_{i}(x)}$ — это произведение всех неприводимых многочленов степени ${\displaystyle i}$, которые делят многочлен ${\displaystyle f(x)}$. Зная степень ${\displaystyle h_{i}(x)}$, можно определить количество таких многочленов, равное ${\displaystyle r_{i}=\deg h_{i}(x)/i}$. Пусть ${\displaystyle h_{i}(x)=p_{1}(x)\dots p_{r_{i}}(x)}$. Если рассмотреть многочлен ${\displaystyle p_{j}(x-z)}$, где ${\textstyle z\in \mathbb {F} _{p}}$, то порядок такого многочлена ${\displaystyle d_{j}}$ в поле ${\textstyle \mathbb {F} _{p^{i}}}$ должен делить число ${\displaystyle p^{i}-1}$. Если ${\displaystyle d_{j}}$ не делится на ${\displaystyle d_{k}}$, то многочлен ${\textstyle x^{d_{j}}-x}$ делится на ${\textstyle p_{j}(x-z)}$, но не на ${\textstyle p_{k}(x-z)}$.

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

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

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

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