Алгоритм Берлекампса - Berlekamps algorithm

Об алгоритме работы с LFSR см. Алгоритм Берлекампа-Месси.

В математика, особенно вычислительная алгебра, Алгоритм Берлекампа хорошо известный метод для факторизация полиномов над конечными полями (также известный как Поля Галуа). Алгоритм состоит в основном из матрица редукция и полином НОД вычисления. Это было изобретено Элвин Берлекамп в 1967 году. Это был доминирующий алгоритм для решения проблемы, пока Алгоритм Кантора – Цассенхауза 1981 года. В настоящее время он реализован во многих известных системы компьютерной алгебры.

Обзор

Алгоритм Берлекампа принимает на вход многочлен без квадратов ${\displaystyle f(x)}$ (то есть без повторяющихся факторов) степени ${\displaystyle n}$ с коэффициентами в конечном поле ${\displaystyle \mathbb {F} _{q}}$ и дает на выходе полином ${\displaystyle g(x)}$ с коэффициентами в том же поле такими, что ${\displaystyle g(x)}$ разделяет ${\displaystyle f(x)}$. Затем алгоритм может быть применен рекурсивно к этим и последующим делителям, пока мы не найдем разложение ${\displaystyle f(x)}$ в полномочия неприводимые многочлены (напоминая, что звенеть многочленов над конечным полем является уникальная область факторизации ).

Все возможные факторы ${\displaystyle f(x)}$ содержатся в факторное кольцо

${\displaystyle R={\frac {\mathbb {F} _{q}[x]}{\langle f(x)\rangle }}.}$

Алгоритм ориентирован на полиномы ${\displaystyle g(x)\in R}$ которые удовлетворяют сравнению:

${\displaystyle g(x)^{q}\equiv g(x){\pmod {f(x)}}.\,}$

Эти многочлены образуют подалгебра R (которое можно рассматривать как ${\displaystyle n}$-мерное векторное пространство над ${\displaystyle \mathbb {F} _{q}}$), называется Подалгебра Берлекампа. Подалгебра Берлекампа интересна тем, что многочлены ${\displaystyle g(x)}$ он содержит удовлетворение

${\displaystyle f(x)=\prod _{s\in \mathbb {F} _{q}}\gcd(f(x),g(x)-s).}$

В общем, не каждый НОД в приведенном выше продукте будет нетривиальным фактором ${\displaystyle f(x)}$, но некоторые из них предоставляют факторы, которые мы ищем.

Алгоритм Берлекампа находит многочлены ${\displaystyle g(x)}$ подходит для использования с вышеуказанным результатом путем вычисления базиса для подалгебры Берлекампа. Это достигается за счет наблюдения, что подалгебра Берлекампа фактически является ядро определенного ${\displaystyle n\times n}$ матрица над ${\displaystyle \mathbb {F} _{q}}$, которая получается из так называемой матрицы Берлекампа многочлена, обозначаемой ${\displaystyle {\mathcal {Q}}}$. Если ${\displaystyle {\mathcal {Q}}=[q_{i,j}]}$ тогда ${\displaystyle q_{i,j}}$ коэффициент при ${\displaystyle j}$-й степени в сокращении ${\displaystyle x^{iq}}$ по модулю ${\displaystyle f(x)}$, то есть:

${\displaystyle x^{iq}\equiv q_{i,n-1}x^{n-1}+q_{i,n-2}x^{n-2}+\ldots +q_{i,0}{\pmod {f(x)}}.\,}$

С некоторым полиномом ${\displaystyle g(x)\in R}$, сказать:

${\displaystyle g(x)=g_{n-1}x^{n-1}+g_{n-2}x^{n-2}+\ldots +g_{0},\,}$

мы можем связать вектор-строку:

${\displaystyle g=(g_{0},g_{1},\ldots ,g_{n-1}).\,}$

Относительно просто увидеть, что вектор-строка ${\displaystyle g{\mathcal {Q}}}$ соответствует, таким же образом, уменьшению ${\displaystyle g(x)^{q}}$ по модулю ${\displaystyle f(x)}$. Следовательно, многочлен ${\displaystyle g(x)\in R}$ находится в подалгебре Берлекампа тогда и только тогда, когда ${\displaystyle g({\mathcal {Q}}-I)=0}$ (куда ${\displaystyle I}$ это ${\displaystyle n\times n}$ единичная матрица ), т.е. тогда и только тогда, когда он находится в нулевом пространстве ${\displaystyle {\mathcal {Q}}-I}$.

Вычисляя матрицу ${\displaystyle {\mathcal {Q}}-I}$ и уменьшив его до сокращенная форма эшелона строки а затем легко считывая базис для нулевого пространства, мы можем найти базис для подалгебры Берлекампа и, следовательно, построить многочлены ${\displaystyle g(x)}$ в этом. Затем нам нужно последовательно вычислить НОД указанной выше формы, пока мы не найдем нетривиальный фактор. Поскольку кольцо многочленов над полем является Евклидова область, мы можем вычислить эти НОД, используя Евклидов алгоритм.

Концептуальное алгебраическое объяснение

С некоторой абстрактной алгеброй идея алгоритма Berlkemap становится концептуально ясной. Представим конечное поле ${\textstyle \mathbb {F} _{q}[x]}$, куда ${\textstyle q=p^{m}}$ для некоторого простого p, поскольку ${\textstyle \mathbb {F} _{p}[y]/(g(y))}$. Можно предположить, что ${\textstyle f(x)\in \mathbb {F} _{q}[x]}$ является бесквадратным, взяв все возможные корни p-й степени и затем вычислив НОД с его производной.

Теперь предположим, что ${\textstyle f(x)=f_{1}(x)\ldots f_{n}(x)}$ - разложение на неприводимые. Тогда у нас есть изоморфизм колец, ${\textstyle \sigma :\mathbb {F} _{q}[x]/(f(x))\to \prod _{i}\mathbb {F} _{q}[x]/(f_{i}(x))}$, задаваемый китайской теоремой об остатках. Ключевое наблюдение состоит в том, что автоморфизм Фробениуса ${\textstyle x\to x^{p}}$ ездит с ${\textstyle \sigma }$, так что если обозначить ${\textstyle {\text{Fix}}_{p}(R)=\{f\in R:f^{p}=f\}}$, тогда ${\textstyle \sigma }$ ограничивается изоморфизмом ${\textstyle {\text{Fix}}_{p}(\mathbb {F} _{q}[x]/(f(x)))\to \prod _{i=1}^{n}{\text{Fix}}_{p}(\mathbb {F} _{q}[x]/(f_{i}(x)))}$. По теории конечного поля ${\textstyle {\text{Fix}}_{p}(\mathbb {F} _{q}[x]/(f_{i}(x))}$ всегда является простым подполем этого расширения поля. Таким образом, ${\textstyle {\text{Fix}}_{p}(\mathbb {F} _{q}[x]/(f(x)))}$ имеет ${\textstyle p}$ элементы тогда и только тогда, когда ${\textstyle f(x)}$ неприводимо.

Более того, мы можем использовать тот факт, что автоморфизм Фробениуса является ${\textstyle \mathbb {F} _{p}}$-линейный для расчета фиксированного набора. То есть отметим, что ${\textstyle {\text{Fix}}_{p}(\mathbb {F} _{q}[x]/(f(x)))}$ это ${\textstyle \mathbb {F} _{p}}$-подпространство, и явный базис для него может быть вычислен в кольце многочленов ${\textstyle \mathbb {F} _{p}[x,y]/(f,g)}$ вычисляя ${\textstyle (x^{i}y^{j})^{p}}$ и установив линейные уравнения на коэффициенты при ${\textstyle x,y}$ многочлены, которые удовлетворяются тогда и только тогда, когда это фиксировано Фробениусом. Отметим, что на данный момент у нас есть эффективно вычислимый критерий неприводимости, и оставшийся анализ показывает, как использовать его для поиска факторов.

Теперь алгоритм разбивается на два случая:

• В случае малых ${\textstyle p}$ мы можем построить любой ${\textstyle g\in {\text{Fix}}_{p}(\mathbb {F} _{q}[x]/(f(x)))\setminus \mathbb {F} _{p}}$, а затем заметьте, что для некоторых ${\textstyle a\in \mathbb {F} _{p}}$ Существуют ${\textstyle i,j}$ так что ${\textstyle g-a=0\mod f_{i}}$ и ${\textstyle g-a\not =0\mod f_{j}}$. Такой ${\textstyle g-a}$ имеет общий нетривиальный фактор с ${\textstyle f(x)}$, который можно вычислить с помощью gcd. В качестве ${\textstyle p}$ маленький, мы можем перебрать все возможные ${\textstyle a}$.
• В случае больших простых чисел, которые обязательно являются нечетными, можно использовать тот факт, что случайный ненулевой элемент из ${\textstyle \mathbb {F} _{p}^{*}}$ квадрат с вероятностью ${\textstyle 1/2}$, и что карта ${\textstyle x\to x^{\frac {p-1}{2}}}$ отображает множество ненулевых квадратов в ${\textstyle 1}$, а множество неквадратов к ${\textstyle -1}$. Таким образом, если взять случайный элемент ${\textstyle g\in {\text{Fix}}_{p}(\mathbb {F} _{q}[x]/f(x))}$, то с хорошей вероятностью ${\textstyle g^{\frac {p-1}{2}}-1}$ будет иметь нетривиальный фактор, общий с ${\textstyle f(x)}$.

Для получения дополнительной информации можно обратиться.^[1]

Приложения

Одним из важных приложений алгоритма Берлекампа является вычисление дискретные логарифмы над конечными полями ${\displaystyle \mathbb {F} _{p^{n}}}$, куда ${\displaystyle p}$ прост и ${\displaystyle n\geq 2}$. Вычисление дискретных логарифмов - важная проблема в криптография с открытым ключом и кодирование с контролем ошибок. Для конечного поля самый быстрый из известных методов - это индексный метод исчисления, который включает факторизацию элементов поля. Если мы представим поле ${\displaystyle \mathbb {F} _{p^{n}}}$ обычным способом - то есть как многочлены над базовым полем ${\displaystyle \mathbb {F} _{p}}$, приведенный по модулю неприводимого многочлена степени ${\displaystyle n}$ - тогда это просто полиномиальная факторизация, как это предусмотрено алгоритмом Берлекампа.

Реализация в системах компьютерной алгебры

Доступ к алгоритму Берлекампа можно получить в пакете PARI / GP с помощью Factormod команда, а Вольфрам Альфа [1] интернет сайт.

Смотрите также

• Полиномиальная факторизация
• Факторизация многочленов над конечным полем и тесты неприводимости
• Алгоритм Кантора – Цассенхауза

Рекомендации

1. "Теория вычислений - Декстер Козен". Springer. Получено 2020-09-19.

• Берлекамп, Элвин Р. (1967). «Факторизация многочленов по конечным полям». Технический журнал Bell System. 46: 1853–1859. Дои:10.1002 / j.1538-7305.1967.tb03174.x. МИСТЕР  0219231. BSTJ Позже переиздан в: Берлекамп, Элвин Р. (1968). Алгебраическая теория кодирования. Макгроу Хилл. ISBN  0-89412-063-8.
• Кнут, Дональд Э (1997). «4.6.2 Факторизация многочленов». Получисловые алгоритмы. Искусство программирования. 2 (Третье изд.). Ридинг, Массачусетс: Эддисон-Уэсли. С. 439–461, 678–691. ISBN  0-201-89684-2.