Алгоритм Берлекэмпа

В математике , в частности, в вычислительной алгебре , алгоритм Берлекэмпа — это хорошо известный метод факторизации многочленов над конечными полями (также известными как поля Галуа ). Алгоритм в основном состоит из редукции матриц и вычисления НОД полиномов . Он был изобретен Элвином Берлекэмпом в 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 Я}$${\displaystyle n\times n}$ ${\displaystyle {\mathcal {Q}}-I}$

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

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

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

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

• В случае малого мы можем построить любой , а затем заметить, что для некоторых существуют , так что и . Такой имеет нетривиальный множитель, общий с , который можно вычислить через gcd. Поскольку является малым, мы можем циклически перебрать все возможные .${\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)}$${\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 и на веб-сайте WolframAlpha [1].

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

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