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

История

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

В алгоритме Берлекэмпа многочлен ${\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}}$ , что вместе с двумя другими решает задачу факторизации .

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

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

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

Алгоритм

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Пример

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

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

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

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

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

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

Время работы

Поэтапно время работы одной итерации алгоритма можно оценить следующим образом, считая степень многочлена равной ${\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)}$ . В частном случае извлечения квадратного корня величина ${\displaystyle n}$ равна двум, поэтому время работы оценивается как ${\displaystyle O(\log p)}$ на одну итерацию алгоритма .

Примечания