Русская Википедия:Алгоритм Берлекэмпа

Материал из Онлайн справочника
Перейти к навигацииПерейти к поиску

Шаблон:Не путать Алгоритм Берлекэмпа — алгоритм, предназначенный для факторизации унитарных многочленов над конечным полем. Разработан Элвином Берлекэмпом в 1967 году. Может использоваться также для проверки неприводимости многочленов над конечными полямиШаблон:Переход. Основная идея алгоритма заключается в возможности представления исходного многочлена в виде произведения наибольших общих делителей самого многочлена и некоторых многочленов, которые с точностью до свободного члена являются <math>f</math>-разлагающими.

Алгоритм Берлекэмпа имеет большую вычислительную сложность, поэтому был разработан ряд дополнительных методов, позволяющих сократить количество необходимых математических операций. Однако, несмотря на свою сложность, алгоритм Берлекэмпа был реализован в системах компьютерной алгебры. Алгоритм нашёл широкое применение в теории кодирования и в изучении линейных рекуррентных соотношений в конечных полях. Имеется много вычислительных задач в алгебре и в теории чисел, которые так или иначе связаны с разложением многочленов над конечными полями, например, разложение на множители многочленов над кольцом целых чисел, отыскание разложения простого рационального числа в поле алгебраических чисел, вычисление группы Галуа некоторого уравнения над полем рациональных чисел и построение расширений полей.

История создания

Американский математик, профессор Калифорнийского университета Берлекэмп занимался изучением циклических кодов обнаружения и исправления ошибок, в том числе кода Боуза — Чоудхури — Хоквингема, свойства которых зависят от делителей порождающих многочленов. Технические достижения Берлекэмпа в области декодирования этих кодов сделали их более привлекательными с практической точки зренияШаблон:Sfn.

Алгоритм был впервые изложен в статье «Factoring Polynomials Over Finite Fields»Шаблон:Sfn и позже воспроизведён в книге «Algebraic Coding Theory»Шаблон:Sfn. В этой работе 1967 года Шаблон:Sfn Берлекэмп пишет, что проблема факторизации возникает в трудах Голомба[1]. Однако, возможность использования матрицы <math>B</math> для определения числа нормированных сомножителей многочлена <math>f(x)</math> была впервые замечена в статье Шаблон:Нп3[2]. В статье Батлера[3] было установлено, что ранг матрицы <math>B-E</math> равен <math>n-k</math>, другое доказательство этого факта было дано Шварцем[4].

Алгоритм Берлекэмпа упоминался во множестве работШаблон:Sfn и являлся основным алгоритмом решения проблемы факторизации до появления в 1981 году Шаблон:Нп3[5]. Была разработана техника[6] позволяющая разложить многочлен на множители за <math> O( n^{(\omega+1)/2+o(1)}+n^{1+o(1)} \log q ),</math> где <math>\omega</math> — показатель в оценке сложности перемножения квадратных матрицШаблон:Sfn.

Постановка и определения

Рассматривается задача факторизации многочлена <math>f(x)</math> степени <math>n</math> (<math>n \ge 2</math>) над конечным полем <math>\mathbb{F}_q</math> (<math>q=p^m</math>, <math>p</math> — простое число)Шаблон:Sfn на различные неприводимые унитарные многочлены <math>f(x) = f_1(x)^{e_1} \cdots f_k(x)^{e_k}</math>.

Для использования в алгоритме строится матрица <math>B=(b_{ij})_{i=0,\;j=0}^{n-1,\; n-1}</math> согласно следующим условиям:

<math>{x^{iq}} \equiv \sum^{n-1}_{j=0} b_{ij} x^j \pmod{f(x)}\quad i=\overline{0,n-1}</math>.

Многочлен <math>h(x) \in \mathbb{F}_q[x]</math> такой, что <math> 1 \leqslant \deg{h(x)} < n, \quad {h(x)}^q \equiv h(x) \pmod{f(x)}</math>, называется <math>f</math>-разлагающим многочленомШаблон:Sfn.

Основной случай

Файл:Основной случай.png
Блок-схема для алгоритма Берлекэмпа — основной случай

Алгоритм факторизации над конечным полем <math>\mathbb{F}_q</math> многочлена вида:

<math>f(x) = f_1(x) \cdots f_k(x)</math>

состоит из следующих шагов:

  1. Вычисление матрицы <math>B</math>Шаблон:Sfn.
  2. Поиск базиса <math>\overline{e_1},\dots ,\overline{e_k}</math> подпространства решений системы линейных уравненийШаблон:Sfn:
    <math>(B-E_n)^T \mathbf x = \mathbf 0</math>,
    при этом удаётся выбрать вектор <math>\overline{e_1} = (1,\;0,\;....\;,\;0)</math>, так как он всегда будет присутствоватьШаблон:Sfn в базисе пространства решений ввиду того, что <math>x^{i q} \equiv 1\pmod{f(x)}</math> при <math>i=0</math>.
  3. Найденное число <math>k</math> есть число неприводимых делителейШаблон:Sfn <math>f(x)</math>.
    • Если <math>k=1</math>, то многочлен является неприводимым.
    • Если <math>k>1</math>, то векторы <math>\overline{e_l}</math> имеют вид <math>(h_{l,\;0}, \dots , h_{l,\;n-1})</math>. По этим числам строятся <math>f</math>-разлагающие многочлены:
      <math>h_l(x) = \sum^{n-1}_{i=0} h_{l,\;i}\;x^i, \quad l=\overline{2,\;k}, \quad h_1(x)=1.</math>.
  4. Поиск разложенияШаблон:Sfn:
    <math>f(x) = \prod_{c \in \mathbb{F}_q, } \gcd(f(x),h_2(x)-c)</math>
    в виде:
    <math>f(x) = \prod_m g_{m,\;2}(x)</math>,
    где <math>g_{m,\;s}(x), \quad s = \overline{2, k}</math> в общем случае не являются неприводимыми. Функции <math>g_{m,\;s}(x)</math> факторизуются таким же способомШаблон:Sfn, то есть:
    <math>g_{m,\;s}(x) = \prod_{c \in \mathbb{F}_q, } \gcd(g_{m,\;s}(x),h_{s+1}(x)-c), \quad s = \overline{2, k-1}</math>.

Общий случай

Файл:Сведение к основному случаю.png
Блок-схема для алгоритма Берлекэмпа — сведение к основному случаю

Задача факторизации произвольного унитарного многочлена сводится к рассмотрению основного случая. Для этого вычисляется многочлен

<math>d(x) = \gcd(f(x),\;f^{'}(x))</math>

с применением алгоритма Евклида.

  • Если <math>d(x) = 1,</math> то многочлен не содержит кратных корней, так как кратный корень одновременно является и корнем производнойШаблон:Sfn.
  • Если <math>d(x) = f(x),</math> то <math>f^{'}(x) = 0,</math> и значит <math>f(x) = g(x)^p,\quad g(x)\in \mathbb{F}_q [x].</math> Если <math>g^{'}(x) = 0,</math> то для <math>g(x)</math> необходимо проделать описанную процедуру до тех пор пока не будет получено разложение <math>f(x) = h(x)^{p^s}, h{'}(x) \ne 0.</math> Многочлен <math>h(x)</math> удовлетворяет требованиям основного случаяШаблон:Sfn.
  • Иначе, многочлен <math>d(x)</math> является нетривиальным делителем многочлена <math>f(x)</math>. В свою очередь, многочлен <math>\frac{f(x)}{d(x)} </math> не имеет кратных неприводимых сомножителейШаблон:Sfn. Если <math>d(x)</math> содержит кратные сомножители, то к нему также применяется описанная процедура. Зная эти разложения, легко получить разложение <math>f(x)</math>.

Таким образом, задача разложения произвольного унитарного многочлена над конечным полем <math> \mathbb{F}_q[x]</math> сводится к разложению на множители конечного числа многочленов, которые не имеют кратных неприводимых сомножителей, то есть к основному случаюШаблон:Sfn.

Обоснование

Пусть:

<math>f(x) = f_1(x)^{e_1} \cdots f_k(x)^{e_k}</math>, где <math>\quad e_i = 1, \quad i=\overline{1,k}</math>.

Согласно китайской теореме об остатках существует единственный многочлен для любого набора <math>(c_1,\;...,\;c_k)</math> элементов поля <math>\mathbb{F}_q</math>Шаблон:Sfn:

<math>h(x)\in \mathbb{F}_q[x],</math>

такой что:

<math>h(x) \equiv c_i \pmod{f_i(x)}, \; i=\overline{1,\;k}, \quad \deg{h(x)} < \deg{f(x)}</math>.

Многочлен <math>h(x)</math> удовлетворяет условиюШаблон:Sfn:

<math>{h(x)} \equiv c_i \equiv c_i^q \equiv h(x)^q \pmod{f_i(x)}, \quad i=\overline{1,\;k}</math>,

и поэтомуШаблон:Sfn:

<math>h(x)^q \equiv h(x) \pmod{f(x)}, \quad \deg{h(x)} < deg{f(x)}</math>.

Из условия:

<math> h(x)^q - h(x) = \prod_{c \in \mathbb{F}_q} (h(x) - c) \equiv 0 \pmod{f(x)}</math>,

и из взаимной простоты сомножителей в правой части следует, что каждый неприводимый делитель многочлена <math>f(x)</math> делит один, и только один из многочленов <math>h(x)-c</math>. Таким образом, доказана справедливость и единственность разложенияШаблон:Sfn:

<math>f(x) = \prod_{c \in \mathbb{F}_q } \gcd(f(x),h(x)-c).</math>

Для нахождения многочлена:

<math>h(x) = a_0 + a_1x^1 + \dots + a_{n-1}x^{n-1} \in \mathbb{F}_q</math>

рассмотрим сравнение:

<math>h(x)^q \equiv h(x) \pmod{f(x)}</math>,

которое равносильно условиюШаблон:Sfn:

<math>\sum_{i=0}^{n-1}a_ix^{iq}\equiv\sum_{i=0}^{n-1}a_ix^i\pmod{f(x)}</math>.

По определению матрицы <math>B</math> получим:

<math>\sum_{i=0}^{n-1}a_i\sum_{j=0}^{n-1}b_{ij}x^j=\sum_{i=0}^{n-1}a_ix^i</math>,

поэтомуШаблон:Sfn:

<math>\sum_{i=0}^{n-1}a_i b_{ij}=a_j, \quad j=\overline{0,\;n-1}</math>.

Полученная система уравнений определяет коэффициенты <math>f</math>-разлагающих многочленов и может быть записана в виде:

<math>\quad(a_0,\;a_1,... ,a_{n-1})B=(a_0,\;a_1,\;... ,a_{n-1})</math>

или:

<math>\quad(a_0,\;a_1,... ,a_{n-1})(B-E_n)=\mathbf0</math>Шаблон:Sfn.

Сложность алгоритма

Сложность алгоритма составляет <math>O(n^3 + qkn)</math> математических операцийШаблон:Sfn. Алгоритм будет эффективен только для небольших полей. Это связано с необходимостью перебора всех <math>c \in \mathbb{F}_q</math>.

Усовершенствования

  • В случае простого поля, если значение <math>p</math> велико, то перебор значений <math>c \in {\mathbb{Z} / p \mathbb{Z}}</math> займёт много времени. Однако, возможно определить множество <math>M</math>, состоящее из <math>c</math>, для которых <math>\gcd(f(x),h(x)-c)</math> нетривиаленШаблон:Sfn. Для этого необходимо найти корни результантаШаблон:Sfn <math>R(c)</math>, которые и будут составлять множество <math>M</math>.
  • Ещё один метод разложения унитарного многочлена <math>f (x) \in GF(q) [x]</math>, не имеющего кратных неприводимых множителей, основан на приведении некоторой эффективно вычислимой с помощью алгоритма Берлекэмпа матрицы A к диагональному видуШаблон:Sfn. Однако сам процесс диагонализации довольно сложен.
  • В работе Калтофена и Лобо[7] была предложена вероятностная версия алгоритма Берлекэмпа, позволяющая разложить на множители многочлен <math>f(x) \in GF(q) [x]</math> степени <math>n</math> за <math>O((n \log n+ \log q) \cdot n (\log n) \log (\log n))</math> арифметических операций. Алгоритм Калтофена — Лобо был реализован на компьютере, и оказался эффективным для многочленов высокой степени, например, для многочленов степени 10001 над полем <math>\mathbb{Z}/127\mathbb{Z}</math> он работает около 102,5 часов на компьютере Sun-4.

Применение

Алгоритмы факторизации многочленов важны для теории кодирования и для изучения линейных рекуррентных соотношений в конечных полях. Также алгоритм Берлекэмпа используется для вычисления группы Галуа уравнения над полем рациональных чисел и построения решений полей, разложения многочленов над кольцом целых чисел, для отыскания разложения простого рационального числа в поле алгебраических чисел, и для некоторых других вычислительных задачШаблон:Sfn. Шаблон:Нп3 используют алгоритмы факторизации многочленов для решения задачи отыскания дискретного логарифмаШаблон:Sfn, на вычислительной сложности которой, построена схема Эль-Гамаля.

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

В системе компьютерной алгебры Шаблон:Iw алгоритм Берлекэмпа может быть использован посредством команды factormod[8].

Примечания

Шаблон:Примечания

Литература

Партнерские ресурсы
Криптовалюты
Магазины
Хостинг
Разное

  1. ↑ Шаблон:Книга
  2. ↑ Шаблон:Статья
  3. ↑ Шаблон:Статья
  4. ↑ Шаблон:Статья
  5. ↑ Шаблон:Книга
  6. ↑ Шаблон:Статья
  7. ↑ Шаблон:Статья
  8. ↑ Catalogue of GP/PARI Functions: Arithmetic functions Шаблон:Webarchive
Источник — http://wikihandbk.com/ruwiki/index.php?title=Русская_Википедия:Алгоритм_Берлекэмпа&oldid=8939970