Berlekampův algoritmus

Berlekampův algoritmus je algoritmus navržený k rozkladu unitárních polynomů přes konečné pole . Navrhl Alvin Berlekamp v roce 1967 . Lze jej také použít k testování neredukovatelnosti polynomů nad konečnými tělesy . Hlavní myšlenkou algoritmu je možnost reprezentovat původní polynom jako součin největších společných dělitelů samotného polynomu a některých polynomů, které se rozšiřují až na volný člen. $F$

Berlekampův algoritmus má vysokou výpočetní náročnost, proto byla vyvinuta řada dalších metod, které snižují počet nezbytných matematických operací. Navzdory své složitosti byl však Berlekampův algoritmus implementován v systémech počítačové algebry. Algoritmus našel široké uplatnění v teorii kódování a při studiu lineárních rekurentních vztahů v konečných polích. V algebře a teorii čísel existuje mnoho výpočetních problémů, které nějak souvisejí s rozkladem polynomů na konečných tělesech, například rozklad polynomů na kruh celých čísel , hledání rozkladu prvočíselného racionálního čísla v oboru algebraických čísel, výpočet Galoisova grupa nějaké rovnice nad oborem racionálních čísel a konstrukce rozšíření pole.

Historie vytvoření

Americký matematik, profesor na Kalifornské univerzitě v Berlekampu, studoval cyklické kódy detekce chyb a opravy , včetně kódu Bose-Chowdhury-Hockwingham , jehož vlastnosti závisí na dělitelích generujících polynomů. Berlekampovy technické pokroky v dekódování těchto kódů je učinily praktičtějšími [1] .

Algoritmus byl poprvé popsán v článku "Factoring Polynomials Over Finite Fields" [2] a později reprodukován v knize "Algebraic Coding Theory" [2] . V tomto článku z roku 1967 [3] Berlekamp píše, že problém faktorizace vyvstává ve spisech Golomba [4] . Možnost použít matici k určení počtu normalizovaných faktorů polynomu však byla poprvé zaznamenána v článku Karla Piotra $B$ $f(x)$ [5] . Butlerův článek [6] zjistil, že hodnost maticeje, další důkaz této skutečnosti podal Schwartz [7] . $BÝT$ $nk$

Algoritmus Berlekamp byl zmíněn v mnoha pracích [8] a byl hlavním algoritmem pro řešení problému faktorizace až do příchodu algoritmu Cantor-Zassenhaus v roce 1981.[9] . Byla vyvinuta technika [10] , která umožňuje faktorizovat polynom v tom, kde je indikátor při odhadu složitosti násobení čtvercových matic [11] . $O(n^{{(\omega +1)/2+o(1)}}+n^{{1+o(1)}}\log q),$ $\omega$

Prohlášení a definice

Je zvažován problém rozkladu polynomu stupně ( ) nad konečným tělesem ( , je prvočíslo ) [12] na různé ireducibilní unitární polynomy . $f(x)$ $n$ $n\geq 2$ $\mathbb {F} _{q}$ $q=p^{m}$ $p$ $f(x)=f_{1}(x)^{{e_{1}}}\cdots f_{k}(x)^{{e_{k}}}$

Pro použití v algoritmu je matice vytvořena podle následujících podmínek: $B=(b_{{ij}})_{{i=0,\;j=0}}^{{n-1,\;n-1}}$

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

Polynom takový, že , se nazývá -rozkládající polynom [13] . $h(x)\in \mathbb {F} _{q}[x]$ $1\leqslant \deg {h(x)}<n,\quad {h(x)}^{q}\equiv h(x){\pmod {f(x)}}$ $F$

Základní případ

Faktorizační algoritmus nad konečným tělesem polynomu ve tvaru: $\mathbb {F} _{q}$

f(x)=f_{1}(x)\cdots f_{k}(x)

se skládá z následujících kroků:

Maticový výpočet [14] . $B$
Hledání základu podprostoru řešení soustavy lineárních rovnic [15] : $\overline {e_{1}},\tečky ,\overline {e_{k}}$ $(B-E_{n})^{T}\mathbf {x} =\mathbf {0}$ , v tomto případě je možné zvolit vektor , protože bude vždy přítomen [15] v základu prostoru řešení vzhledem k tomu, že při . $\overline {e_{1}}=(1,\;0,\;....\;,\;0)$ $x^{iq}\equiv 1{\pmod {f(x)))$ $i=0$
Nalezené číslo je počet ireducibilních dělitelů [14] . $k$ $f(x)$
- Jestliže , pak je polynom
ireducibilní . $k=1$
Jestliže , pak vektory mají tvar . Tato čísla se používají ke konstrukci rozkládajících polynomů: $k>1$ $\overline {e_{l}}$ $(h_{{l,\;0}},\tečky ,h_{{l,\;n-1}})$ $F$ $h_{l}(x)=\sum _{i=0}^{n-1}h_{l,\;i}\;x^{i},\quad l={\overline {2 ,\;k}},\quad h_{1}(x)=1.$ .
Dekompoziční vyhledávání [15] : $f(x)=\prod _{{c\in {\mathbb {F}}_{q},}}\gcd(f(x),h_{2}(x)-c)$ tak jako: $f(x)=\prod _{m}g_{{m,\;2}}(x)$ , kde v obecném případě nejsou neredukovatelné. Funkce jsou faktorizovány stejným způsobem [15] , tj. $g_{{m,\;s}}(x),\quad s=\overline {2,k}$ $g_{{m,\;s}}(x)$ $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}$ .

Obecný případ

Problém faktorizace libovolného unitárního polynomu je redukován na zvážení hlavního případu. K tomu se vypočítá polynom

d(x)=\gcd(f(x),\;f^{{'}}(x))

pomocí Euklidova algoritmu .

Jestliže pak polynom neobsahuje více kořenů, protože násobný kořen je také kořenem derivace [16] . $d(x)=1,$
If then znamená If then for je nutné provést popsaný postup, dokud nedosáhneme rozšíření Polynom splňuje požadavky hlavního případu [16] . $d(x)=f(x),$ $f^{{'}}(x)=0,$ $f(x)=g(x)^{p},\quad g(x)\in \mathbb {F} _{q}[x].$ $g^{{'}}(x)=0,$ $g(x)$ $f(x)=h(x)^{{p^{s}}},h{'}(x)\neq 0.$ $h(x)$
Jinak je polynom netriviálním dělitelem polynomu . Na druhé straně polynom nemá žádné vícenásobné neredukovatelné faktory [16] . Pokud obsahuje více faktorů, pak se popsaný postup aplikuje i na něj. Se znalostí těchto rozšíření je snadné získat rozšíření . $d(x)$ $f(x)$ ${\frac {f(x)}{d(x)))$ $d(x)$ $f(x)$

Problém faktorizace libovolného unitárního polynomu nad konečným tělesem je tedy redukován na faktorizaci konečného počtu polynomů, které nemají více neredukovatelných faktorů, tedy na hlavní případ [16] . $\mathbb {F} _{q}[x]$

Odůvodnění

Nechat:

f(x)=f_{1}(x)^{{e_{1}}}\cdots f_{k}(x)^{{e_{k}}}

, kde .

\quad e_{i}=1,\quad i=\overline {1,k}

Podle čínské věty o zbytku existuje pro jakoukoli sadu prvků pole jedinečný polynom [17] : $(c_{1},\;...,\;c_{k})$ $\mathbb {F} _{q}$

h(x)\in {\mathbb {F}}_{q}[x],

takové, že:

h(x)\equiv c_{i}{\pmod {f_{i}(x))),\;i=\overline {1,\;k},\quad \deg {h(x)}<\ stupeň{f(x)}

Polynom splňuje podmínku [17] : $h(x)$

{h(x)}\equiv c_{i}\equiv c_{i}^{q}\equiv h(x)^{q}{\pmod {f_{i}(x)))),\quad i = \overline {1,\;k}

a tak [18] :

{\displaystyle h(x)^{q}\equiv h(x){\pmod {f(x)))),\quad \deg {h(x)}<deg{f(x))))

Z podmínky:

h(x)^{q}-h(x)=\prod _{{c\in {\mathbb {F}}_{q}}}(h(x)-c)\equiv 0{\pmod { f(x)}}

a ze skutečnosti, že faktory na pravé straně jsou koprimé, vyplývá, že každý ireducibilní dělitel polynomu dělí jeden a pouze jeden z polynomů . Platnost a jednoznačnost rozkladu [18] je tedy prokázána : $f(x)$ $h(x)-c$

f(x)=\prod _{{c\in {\mathbb {F}}_{q}}}\gcd(f(x),h(x)-c).

Chcete-li najít polynom:

h(x)=a_{0}+a_{1}x^{1}+\tečky +a_{{n-1}}x^{{n-1}}\in {\mathbb {F}}_ {q}

Podívejme se na srovnání:

h(x)^{q}\equiv h(x){\pmod {f(x)))

což je ekvivalentní podmínce [17] :

\sum _{{i=0}}^{{n-1}}a_{i}x^{{iq}}\equiv \sum _{{i=0}}^{{n-1}}a_ {i}x^{i}{\pmod {f(x)))

Definicí matice dostaneme: $B$

\součet _{{i=0}}^{{n-1}}a_{i}\součet _{{j=0}}^{{n-1}}b_{{ij}}x^{j }=\sum _{{i=0}}^{{n-1}}a_{i}x^{i}

takže [17] :

\sum _{i=0}^{n-1}a_{i}b_{ij}=a_{j},\quad j={\overline {0,\;n-1))

Výsledný systém rovnic určuje koeficienty -rozkladných polynomů a lze jej zapsat jako: $F$

\quad (a_{0},\;a_{1},...,a_{{n-1}})B=(a_{0},\;a_{1},\;...,a_ {{n-1}})

nebo:

\quad (a_{0},\;a_{1},...,a_{n-1})(B-E_{n})=\mathbf {0}

[17] .

Složitost algoritmu

Složitost algoritmu jsou matematické operace [19] . Algoritmus bude účinný pouze pro malá pole. Je to kvůli potřebě vyjmenovat všechny . $O(n^{3}+qkn)$ ${\displaystyle c\in \mathbb {F} _{q))$

Vylepšení

V případě jednoduchého pole, pokud je hodnota velká, bude iterace hodnot trvat dlouho. Je však možné definovat množinu sestávající z čehož je netriviální [20] . K tomu je nutné najít kořeny výslednice [21] , ze kterých se bude skládat množina . $p$ $c\in {\mathbb {Z} /p\mathbb {Z} }$ $M$ $C$ $\gcd(f(x),h(x)-c)$ $R(c)$ $M$
Další způsob rozkladu unitárního polynomu , který nemá více ireducibilních faktorů, je založen na redukci nějaké matice A, která je efektivně vyčíslitelná pomocí Berlekampova algoritmu, na diagonální tvar [22] . Samotný proces diagonalizace je však poměrně komplikovaný. $f(x)\in GF(q)[x]$
Kaltofen a Lobo [23] navrhli pravděpodobnostní verzi Berlekampova algoritmu, která umožňuje faktorizovat polynom stupně v aritmetických operacích. Algoritmus Kaltofen-Lobo byl implementován na počítači a ukázal se být účinný pro polynomy vysokého stupně, například pro polynomy stupně 10001 pracuje na poli asi 102,5 hodiny na počítači Sun-4 . $f(x)\in GF(q)[x]$ $n$ $O((n\log n+\log q)\cdot n(\log n)\log(\log n))$ $\mathbb {Z} /127\mathbb {Z}$

Aplikace

Polynomiální faktorizační algoritmy jsou důležité pro teorii kódování a pro studium lineárních rekurentních vztahů v konečných polích. Algoritmus Berlekamp se také používá k výpočtu Galoisovy grupy rovnice nad polem racionálních čísel a konstrukci řešení polí, rozšíření polynomů v kruhu celých čísel, k nalezení rozkladu jednoduchého racionálního čísla v oboru algebraických čísel, a pro některé další výpočetní problémy [24] . Algoritmy s faktorovými bázemipoužijte polynomiální faktorizační algoritmy k řešení problému nalezení diskrétního logaritmu [25] , na jehož výpočetní složitosti je schéma ElGamal postaveno .

Implementace v systémech počítačové algebry

V systému počítačové algebry PARI/GP lze Berlekampův algoritmus použít s příkazem factormod[26] .

Poznámky

↑ Berlekamp, 1967 , str. 1854: „O cyklických kódech“.
↑ 12 Berlekamp , 1967 .
↑ Berlekamp, 1967 , str. 1853.
↑ Golomb, Solomon Wolf. Sekvence posuvného registru . — Egejský park Pr; Upravené vydání, 1981. - 274 s. — ISBN 978-0894120480 .
↑ PETR K. Uber die Reduzibilitat eines Polynoms mit ganzzahligen Koeffi-zienten nach einem Primzahlmodul. — Casopis Pest Mat. Fys, 1937, str. 85-94 .
↑ Butler, MCR O redukovatelnosti polynomů v konečném poli. - The Quarterly Journal of Mathematics Oxford Second Series 5, 1954. - S. 102-107 .
↑ Schwarz, St. O redukovatelnosti polynomů nad konečným tělesem. — Quart. J Math. Oxford Ser. (2) 7, 1956. - str. 110-124 .
↑ Lidl, 1988 , Historický komentář, str. 223-224.
↑ Cantor DG, Zassenhaus H. Nový algoritmus pro faktorování polynomů nad konečnými tělesy. — Matematika. Comp., 1981. Vol. 36. - S. 587-592.
↑ von zur Gathen J., Shoup V. Počítání Frobeniových map a faktoringové polynomy. — Počítač. Complexity, 1992. - svazek 2 . - S. 187-224 .
↑ Vasilenko, 2003 , s. 185: "Složitost algoritmu Cantor-Zassenhaus".
↑ Lidl, 1988 , Vyjádření k problému, str. 187.
↑ Vasilenko, 2003 , Definice, str. 172.
↑ 1 2 Vasilenko, 2003 , Popis algoritmu, str. 173.
↑ 1 2 3 4 Lidl, 1988 , Popis algoritmu.
↑ 1 2 3 4 Lidl, 1988 , Redukce na hlavní věc, str. 188.
↑ 1 2 3 4 5 Lidl, 1988 , Zdůvodnění správnosti algoritmu, str. 189-190.
↑ 1 2 Vasilenko, 2003 , s. 174.
↑ Vasilenko, 2003 , s. 174: "Složitost algoritmu."
↑ Lidl, 1988 , Více o metodě, str. 201.
↑ Van der Waerden, 1976 , O výsledku, s. 124.
↑ Lidl, 1988 , Více o metodě, str. 206.
↑ Kaltofen E, Lobo A. Factoring high-degree polynomials by the black box Berlekamp algorithm // Sborník z mezinárodního sympozia o symbolických a algebraických výpočtech (ISSAC '94). - N. Y .: ACM Press, 1994. - S. 90-98 . — ISBN 0-89791-638-7 . - doi : 10.1145/190347.190371 .
↑ Lidl, 1988 , Aplikace algoritmu, str. 187.
↑ Vasilenko, 2003 , O použití algoritmů s faktorovými bázemi pro řešení problému diskrétního logaritmu, str. 137.
↑ Katalog funkcí GP/PARI: Aritmetické funkce Archivováno 11. března 2007.

Literatura

Berlekamp, Elwyn R. Faktorování polynomů nad konečnými poli // Bell System Technical Journal. - 1967. - Sv. 46 . - S. 1853-1859 . BSTJ později znovu publikováno v: Berlekamp, Elwyn R. Algebraic Coding Theory . - McGraw-Hill Education , 1968. - ISBN 0-89412-063-8 .
Vasilenko O. N. Číselné teoretické algoritmy v kryptografii . - M. : MTSNMO, 2003. - 328 s. — ISBN 5-94057-103-4 .
Lidl R. , Niederreiter G. Konečná pole = Konečná pole / Ed. V. I. Něčajev. - 1. vyd. - M .: Mir, 1988. - T. 1. - 430 s. — ISBN 5-03-000065-8 .
Van der Waerden B.L. Algebra . — M.: Nauka, 1976. — 646 s. Archivováno2. listopadu 2013 naWayback Machine