Журнал фильтра правок

'{{Не путать|алгоритм Берлекэмпа — Мэсси|алгоритмом Берлекэмпа — Мэсси|алгоритмом, предназначенным для нахождения реккурентных зависимостей в последовательностях}} '''Алгоритм Берлекэмпа''' — алгоритм, предназначенный для [[факторизация|факторизации]] [[Унитарный многочлен|унитарных многочленов]] над [[конечное поле|конечным полем]]. Разработан [[Берлекэмп, Элвин|Элвином Берлекэмпом]] в [[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>-разлагающим многочленом{{sfn|Василенко|2003|с=172}}{{sfn|Лидл|1988|с=189}}. == Основной случай == Алгоритм факторизации над конечным полем <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>d(x) = \gcd(f(x),\;f^'(x))</math><br /> с применением [[Алгоритм Евклида|алгоритма Евклида]].<br /> * Если <math>d(x) = 1,</math> то многочлен не содержит кратных корней, так как кратный корень одновременно является и корнем производной.<br /> * Если <math>d(x) = f(x),</math> то <math>f^'(x) = 0,</math> и значит <math>f(x) = g(x)^p,\quad g(x)\in \Bbb{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> удовлетворяет требованиям основного случая.<br /> * Иначе, многочлен <math>d(x)</math> является нетривиальным делителем многочлена <math>f(x).</math> В свою очередь, многочлен <math>\frac{f(x)}{d(x)} </math> не имеет кратных неприводимых сомножителей. Если <math>d(x)</math> содержит кратные сомножители, то к нему также применяется описанная процедура. Зная эти разложения, легко получить разложение <math>f(x).</math><br /> Итак, задача разложения произвольного унитарного многочлена над конечным полем <math> \Bbb{F}_q[x]</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><br /> [[китайская теорема об остатках|Cогласно китайской теореме об остатках]] существует единственный многочлен для любого набора <math>(c_1,\;...,\;c_k)</math> элементов поля <math>\mathbb{F}_q,</math>: : <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> удовлетворяет условию: : <math>{h(x)} \equiv c_i \equiv c_i^q \equiv h(x)^q \pmod{f_i(x)}, \quad i=\overline{1,\;k}</math>, и поэтому: : <math>h(x)^q \equiv h(x) \pmod f(x), \quad \deg{h(x)} < deg{f(x)}.</math><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> Таким образом, доказана справедливость и единственность разложения: : <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>, которое равносильно условию: : <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>, поэтому: : <math>\sum_{i=0}^{n-1}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><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>. == Усовершенствования == * В случае простого поля, если значение <math>p</math> велико, то перебор значений <math>c \in {\Bbb{Z} / p \Bbb{Z}}</math> займёт много времени. Однако, возможно определить множество <math>M</math>, состоящее из <math>c</math>, для которых <math>\gcd(f(x),h(x)-c)</math> нетривиален. Для этого необходимо найти корни результанта <math>R(c)</math>, которые и будут составлять множество <math>M</math>. * Ещё один метод разложения унитарного многочлена <math>f (x) \in GF(q) [x]</math>, не имеющего кратных неприводимых множителей, основан на приведении некоторой эффективно вычислимой с помощью алгоритма Берлекэмпа матрицы A к диагональному виду. Однако сам процесс диагонализации довольно сложен. * В работе Калтофена и Лобо была предложена вероятностная версия алгоритма Берлекэмпа, позволяющая разложить на множители многочлен <math>f(x) \in GF(q) [x]</math> степени <math>n</math> за <math>O((n \log n+ \log q) n(\log n)2 \log \log n)</math>{{уточнить}} арифметических операций. Алгоритм Калтофена — Лобо был реализован на компьютере, и действительно оказался эффективным для многочленов высокой степени, например, для многочленов степени 10001 над полем <math>\Bbb{Z}/127\Bbb{Z}</math> он работает около 102,5 часов на компьютере [[Sun-4]]. == Примечания == {{Примечания}} == Литература == * {{Cite journal |first=Elwyn R. |last=Berlekamp |title=Factoring Polynomials Over Finite Fields |journal=[[Bell System Technical Journal]] |volume=46 |issue= |pages=1853–1859 |year=1967 |ref = Berlekamp |mr=0219231}} [http://www.alcatel-lucent.com/bstj/vol46-1967/articles/bstj46-8-1853.pdf BSTJ] Later republished in: {{Cite book |first=Elwyn R. |last=Berlekamp |title=Algebraic Coding Theory |location= |publisher=McGraw Hill |year=1968 |isbn=0-89412-063-8 }} * {{книга | автор = {{nobr|Василенко О. Н.}} | заглавие = Теоретико-числовые алгоритмы в криптографии | ссылка = http://window.edu.ru/resource/845/23845/files/book.pdf | место = М. | издательство = МЦНМО | год = 2003 | страниц = 328 | isbn = 5-94057-103-4 | ref = Василенко }} * {{книга | автор = {{nobr|Лидл Р.}}, {{nobr|Нидеррайтер Г.}} | заглавие = Конечные поля | оригинал = Finite Fields | ссылка = http://eknigi.org/estestvennye_nauki/123549-konechnye-polya.html | издание = 1-е изд | ответственный = Под ред. В. И. Нечаева | место = М. | издательство = Мир | год = 1988 | том = 1 | страниц = 430 | isbn = 5-03-000065-8 | ref = Лидл }} * {{книга | автор = {{nobr|Ван дер Варден Б.Л.}} | заглавие = Алгебра | ссылка = http://mburyakov.ru/phtf/lib/Varden.pdf | место = M. | издательство = Наука | год = 1976 | страниц = 646 | ref = Ван дер Варден }} {{rq|refless|isbn}} [[Категория:Вычислительная алгебра]] [[Категория:Алгоритмы]]'