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

Метод Берлекэмпа — вероятностный метод нахождения корней многочленов над полем $\mathbb {Z} _{p}$ с полиномиальной сложностью. Метод был описан Берлекэмпом в 1970 году в качестве побочного к алгоритму факторизации многочленов над конечными полями и позже доработан Рабином для случая произвольных конечных полей в 1979 году. До Берлекэмпа метод был независимо открыт некоторыми другими исследователями.

История

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

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

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

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

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

1. Одночлен равен $x$ если $\lambda =0$,
2. Одночлен делит ${\textstyle g_{0}(x)=(x^{(p-1)/2}-1)}$ если $\lambda$ — квадратичный вычет по модулю $p$,
3. Одночлен делит ${\textstyle 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. Вычисляются остатки от деления ${\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)$,
3. Двоичным возведением в степень вычисляется остаток от деления ${\textstyle x^{(p-1)/2}}$ на ${\textstyle f_{z}(x)}$ с использованием посчитанных на прошлом шаге многочленов,
4. Если ${\textstyle x^{(p-1)/2}\not \equiv \pm 1{\pmod {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}$, а не только тех, которые разбиваются в произведение мономов.

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

Пусть нужно решить сравнение ${\textstyle x^{2}\equiv a{\pmod {p}}}$, решениями которого являются элементы $\beta$ и $-\beta$ соответственно. Их нахождение эквивалентно факторизации многочлена ${\textstyle 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 )$. Это позволяет записать решение в виде ${\textstyle \beta =(t-z){\pmod {p}}}$.

Пример

Пусть нужно решить сравнение ${\textstyle x^{2}\equiv 5{\pmod {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$, откуда ${\textstyle \gcd(x^{2}-4x-1;x^{5}-1)\equiv x-9{\pmod {11}}}$. Отсюда ${\textstyle x-9=x-2-\beta }$, значит $\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}}}$.

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

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

Время работы

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

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

Таким образом, вся процедура может быть произведена за время $O(n^{2}\log p)$. Используя быстрое преобразование Фурье и Half-GCD алгоритм, можно улучшить время работы алгоритма до $O(n\log n\log pn)$. В частном случае извлечения квадратного корня величина $n$ равна двум, поэтому время работы оценивается как $O(\log p)$ на одну итерацию алгоритма.