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

Элвин Р. Берлекамп на конференции по комбинаторной теории игр на Международной исследовательской станции Банф Элвин Берлекамп

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

История

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

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

Позволять $p$ быть нечетным простым числом. Рассмотрим полином ${\textstyle f(x)=a_{0}+a_{1}x+\cdots +a_{n}x^{n}}$ над полем $\mathbb {F} _{p}\simeq \mathbb {Z} /p\mathbb {Z}$ остатков по модулю $p$. Алгоритм должен найти все $\lambda$ в $\mathbb {F} _{p}$ такой, что ${\textstyle f(\lambda )=0}$ в $\mathbb {F} _{p}$.

Алгоритм

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

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

Классификация $\mathbb {F} _{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$ является квадратичным неостатком по модулю $p$.

Таким образом, если $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}},\ldots ,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 {F} _{p}$ тогда при расчете $\gcd$ с $g_{0}(x)$ и $g_{1}(x)$ получим нетривиальную факторизацию $f_{z}(x)/g_{z}(x)$, таким образом алгоритм позволяет найти все корни произвольных многочленов над $\mathbb {F} _{p}$.

Модульный квадратный корень

Рассмотрим уравнение ${\textstyle x^{2}\equiv a{\pmod {p}}}$ наличие элементов $\beta$ и $-\beta$ как его корни. Решение этого уравнения эквивалентно факторизации многочлена ${\textstyle f(x)=x^{2}-a=(x-\beta )(x+\beta )}$ над $\mathbb {F} _{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},\ldots ,z+\lambda _{n}$ одновременно являются квадратичными остатками или невычетами. Согласно теории циклотомии , вероятность такого события для случая, когда $\lambda _{1},\ldots ,\lambda _{n}$ все являются остатками или неостатками одновременно (то есть, когда $z=0$ потерпит неудачу) можно оценить как $2^{-k}$ где $k$ количество различных значений в $\lambda _{1},\ldots ,\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=2$, таким образом, вся сложность алгоритма в таком случае ограничивается $O(\log p)$ за итерацию.