Просмотр отдельных изменений

'{{редактирую|[[User:2pizza nazya|Nazariy]] 18:28, 26 октября 2013 (UTC)|26 октября 2013}} {{Не путать|алгоритм Берлекэмпа — Мэсси|алгоритмом Берлекэмпа — Мэсси|алгоритмом, предназначенным для нахождения реккурентных зависимостей в последовательностях}} '''Алгоритм Берлекэмпа''' — алгоритм, предназначенный для [[факторизация|факторизации]] [[Унитарный многочлен|унитарных многочленов]] над [[конечное поле|конечным полем]]. Разработан [[Берлекэмп, Элвин|Элвином Берлекэмпом]] в [[1967 год в науке|1967 году]]. Может использоваться также для проверки [[Неприводимый многочлен|неприводимости многочленов]] над конечными полями{{Переход|#Проверка неприводимости}}. == Постановка и определения == Рассматривается задача факторизации многочлена <math>f(x)</math> [[Степень многочлена|степени]] <math>n</math> (<math>n \ge 2</math>) над конечным полем <math>\Bbb{F}_q</math> (<math>q=p^m</math>, <math>p</math> — простое число) на различные неприводимые унитарные многочлены <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^i}^q \equiv \sum^{n-1}_{j=0} b_{ij} x^i \pmod{f(x)}\quad i=\overline{1,n-1}</math>. Многочлен <math>h(x) \in \Bbb{F}_q</math> такой, что <math> 1 \leqslant \deg{h(x)} < n, \quad {h(x)}^q \equiv h(x) \pmod{f(x)} \quad </math>, называется <math>f</math>-разлагающим многочленом. == Основной случай == Алгоритм факторизации над конечным полем <math>\Bbb{F}_q</math> многочлена вида: : <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>B</math>. # Поиск базиса <math>\overline{e_1},\dots ,\overline{e_k}</math> подпространства решений системы линейных уравнений: #:: <math>(B-E_n)^T \bold x = \bold 0</math>, #: при этом удаётся выбрать вектор <math>\overline{e_1} = (1,\;0,\;....\;,\;0)</math>, так как он всегда будет присутствовать в базисе пространства решений ввиду того что <math>{x^i}^q \equiv 1\pmod{f(x)}</math> при <math>i=0</math>. # Найденное число <math>k</math> есть число неприводимых делителей <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}</math>. # Поиск разложения: #:: <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> факторизуются таким же способом, то есть: #:: <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> == Общий случай == {{Раздел не написан}} == Обоснование == Пусть<br /> :<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><br /> [[китайская теорема об остатках|Cогласно китайской теореме об остатках]] существует единственный многочлен для любого набора <math>(c_1,\;...,\;c_k)</math> элементов поля <math>\mathbb{F}_q,</math> <br /> :<math>h(x)\in \mathbb{F}_q[x],</math><br /> такой что<br /> :<math>h(x) \equiv c_i \pmod{f_i(x)}, \; i=\overline{1,\;k}, \quad \deg{h(x)} < \deg{f(x)}.</math><br /> Многочлен <math>h(x)</math> удовлетворяет условию:<br /> :<math>{h(x)} \equiv c_i \equiv c_i^q \equiv h(x)^q \pmod{f_i(x)}, \quad i=\overline{1,\;k},</math><br /> и поэтому<br /> :<math>h(x)^q \equiv h(x) \pmod f(x), \quad \deg{h(x)} < deg{f(x)}.</math><br /> Из условия<br /> :<math> h(x)^q - h(x) = \prod_{c \in \mathbb{F}_q} (h(x) - c) \equiv 0 \pmod{f(x)},</math><br /> и из взаимной простоты сомножителей в правой части следует, что каждый неприводимый делитель многочлена <math>f(x)</math> делит один, и только один из многочленов <math>h(x)-c.</math> Таким образом, доказана справедливость и единственность разложения<br /> :<math>f(x) = \prod_{c \in \mathbb{F}_q } \gcd(f(x),h(x)-c).</math><br /> Для нахождения многочлена<br /> :<math>h(x) = a_0 + a_1x^1 + \dots + a_{n-1}x^{n-1} \in \mathbb{F}_q</math><br /> рассмотрим сравнение<br /> :<math>h(x)^q \equiv h(x) \pmod{f(x)},</math><br /> которое равносильно условию<br /> :<math>\sum_{i=0}^{n-1}a_ix^{iq}\equiv\sum_{i=0}^{n-1}a_ix^i\pmod{f(x)}.</math><br /> По определению матрицы <math>B</math> получим:<br /> :<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><br /> поэтому<br /> :<math>\sum_{i=0}^{n-1}b_{ij}=a_j, \quad j=\overline{0,\;n-1}.</math><br /> Полученная система уравнений определяет коэффициенты <math>f</math>-разлагающих многочленов и может быть записана в виде:<br /> :<math>\quad(a_0,\;a_1,... ,a_{n-1})B=(a_0,\;a_1,\;... ,a_{n-1})</math><br /> или<br /> :<math>\quad(a_0,\;a_1,... ,a_{n-1})(B-E_n)=\bold0.</math> == Сложность алгоритма == [[Вычислительная сложность|Сложность алгоритма]] составляет <math>O(n^3 + qkn)</math> математических операций. Алгоритм будет эффективен только для небольших полей. Это связанно с необходимостью перебора всех <math>c \in \Bbb{F}_q</math>. == Усовершенствования == {{Раздел не написан}} == Литература == * Berlekamp, Elwyn R. (1967). «Factoring Polynomials Over Finite Fields». Bell Systems Technical Journal 46: 1853—1859. Later republished in: Berlekamp Elwyn R. Algebraic Coding Theory. — McGraw Hill, 1968. * Василенко О. Н. Теоретико-числовые алгоритмы в криптографии. — М.: МЦНМО, 2003. — 328 с. ISBN 5-94057-103-4 {{rq|refless|isbn}} [[Категория:Вычислительная алгебра]] [[Категория:Алгоритмы]]'