Berlekamp algoritmusa

A Berlekamp -algoritmus egy olyan algoritmus, amely az unitárius polinomok véges mező feletti faktorizálására szolgál . Alvin Berlekamp tervezte 1967 - ben . Használható polinomok irreducibilitásának tesztelésére is véges mezőkön . Az algoritmus fő gondolata az a lehetőség, hogy az eredeti polinomot magának a polinomnak a legnagyobb közös osztóinak és néhány olyan polinomnak a szorzataként ábrázoljuk, amelyek egy szabad tagig bővülnek. $f$

A Berlekamp-féle algoritmus nagy számítási bonyolultságú, ezért számos további módszert fejlesztettek ki a szükséges matematikai műveletek számának csökkentésére. Bonyolultsága ellenére azonban Berlekamp algoritmusát számítógépes algebrai rendszerekben is megvalósították. Az algoritmus széles körben alkalmazható a kódoláselméletben és a véges mezők lineáris ismétlődési összefüggéseinek vizsgálatában. Számos számítási probléma van az algebrában és a számelméletben, amelyek valamilyen módon összefüggenek a polinomok véges mezők feletti felosztásával, például polinomok faktorálása egész számok gyűrűjére, egy prímracionális szám felbontásának megtalálása algebrai számok területén, számítás valamely egyenlet Galois-csoportja a racionális számok mezője és a mezőbővítések szerkesztése felett.

Létrehozási előzmények

Egy amerikai matematikus, a Berlekamp- i Kaliforniai Egyetem professzora ciklikus hibaészlelési és -javító kódokat tanulmányozott , beleértve a Bose-Chowdhury-Hockwingham kódot , amelynek tulajdonságai a generáló polinomok osztóitól függenek. Berlekamp technikai fejlődése ezen kódok dekódolásában praktikusabbá tette azokat [1] .

Az algoritmust először a "Factoring Polynomials Over Finite Fields" [2] cikkben írták le, majd az "Algebraic Coding Theory" [2] című könyvben reprodukálták . Ebben az 1967-es cikkben [3] Berlekamp azt írja, hogy a faktorizációs probléma felmerül Golomb [4] írásaiban . A mátrix használatának lehetőségét azonban egy polinom normalizált tényezőinek meghatározására először Karel Piotr cikkében vette észre. $B$ $f(x)$ [5] . Butler cikke [6] megállapította, hogy a mátrix rangja az,erre a tényre egy másik bizonyítékot Schwartz [7] adott . $LENNI$ $nk$

A Berlekamp-algoritmust számos mű említi [8] , és a faktorizációs probléma megoldásának fő algoritmusa volt egészen a Cantor-Zassenhaus algoritmus 1981-es megjelenéséig.[9] . Kifejlesztettek egy technikát [10] , amely lehetővé teszi egy polinom faktorálását,ahol a négyzetmátrixok összetettségének becsléséhez mutató [11] . $O(n^{{(\omega +1)/2+o(1)}}+n^{{1+o(1)}}\log q),$ $\omega$

Nyilatkozat és meghatározások

Megvizsgáljuk egy ( ) fokos polinom véges mezőn ( , egy prímszám ) [12] különböző irreducibilis unitér polinomokká való faktorizálásának problémáját . $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}}}$

Az algoritmusban való felhasználáshoz egy mátrixot építenek fel a következő feltételek szerint: $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}}

Egy olyan polinomot , amelyre , -dekompozíciós polinomnak nevezzük [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$

Alapeset

Faktorizációs algoritmus egy polinom véges mezején a következő alakban: $\mathbb {F} _{q}$

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

a következő lépésekből áll:

Mátrix számítás [14] . $B$
Keresse meg a lineáris egyenletrendszer megoldási alterének alapját [15] : $\overline {e_{1}},\dots ,\overline {e_{k}}$ $(B-E_{n})^{T}\mathbf {x} =\mathbf {0}$ , ebben az esetben lehetőség van a vektor kiválasztására , mivel az mindig jelen lesz [15] a megoldási tér alapjában annak következtében, hogy -nél . $\overline {e_{1}}=(1,\;0,\;....\;,\;0)$ $x^{iq}\equiv 1{\pmod {f(x)))$ $i=0$
A talált szám az irreducibilis osztók száma [14] . $k$ $f(x)$
- Ha , akkor a polinom
irreducibilis . $k=1$
Ha , akkor a vektorok alakja . Ezeket a számokat használjuk felbontó polinomok létrehozására: $k>1$ $\overline {e_{l}}$ $(h_{{l,\;0}},\dots ,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.$ .
Dekompozíciós keresés [15] : $f(x)=\prod _{{c\in {\mathbb {F}}_{q},}}\gcd(f(x),h_{2}(x)-c)$ mint: $f(x)=\prod _{m}g_{{m,\;2}}(x)$ , ahol általános esetben nem redukálhatatlanok. A függvények faktorizálása ugyanúgy történik [15] , azaz: $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}$ .

Általános eset

Egy tetszőleges unitárius polinom faktorizálásának problémája a főeset figyelembevételére redukálódik. Ehhez a polinomot számítjuk ki

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

az Euklidész algoritmus segítségével .

Ha akkor a polinom nem tartalmaz több gyöket, mivel a többszörös gyök egyben a derivált gyöke is [16] . $d(x)=1,$
Ha akkor azt jelenti , hogy Ha akkor a leírt eljárást addig kell végezni, amíg a bővítést meg nem kapjuk. A polinom kielégíti a főeset követelményeit [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)$
Egyébként a polinom a polinom nem triviális osztója . A polinomnak viszont nincs több irreducibilis tényezője [16] . Ha több tényezőt tartalmaz, akkor a leírt eljárást alkalmazzuk rá is. Ezen bővítések ismeretében könnyű megszerezni a bővítést . $d(x)$ $f(x)$ ${\frac {f(x)}{d(x)))$ $d(x)$ $f(x)$

Így egy tetszőleges unitárius polinom véges mezőre való faktorálásának problémája véges számú olyan polinom faktorálására redukálódik, amelyeknek nincs több irreducibilis tényezője, vagyis a főesetre [16] . $\mathbb {F} _{q}[x]$

Indoklás

Legyen:

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

, hol .

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

A kínai maradéktétel szerint a mezőelemek bármely halmazára létezik egy egyedi polinom [17] : $(c_{1},\;...,\;c_{k})$ $\mathbb {F} _{q}$

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

oly módon, hogy:

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

A polinom teljesíti a [17] feltételt : $h(x)$

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

és így [18] :

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

A feltételből:

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

és abból, hogy a jobb oldali faktorok koprímek, az következik, hogy a polinom minden irreducibilis osztója egy és csak egy polinomot oszt . Így a dekompozíció [18] érvényessége és egyedisége bizonyítást nyer : $f(x)$ $h(x)-c$

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

Polinom kereséséhez:

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

Nézzük az összehasonlítást:

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

ami egyenértékű a [17] feltétellel :

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

A mátrix definíciója alapján a következőket kapjuk: $B$

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

szóval [17] :

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

Az eredményül kapott egyenletrendszer meghatározza a -dekomponáló polinomok együtthatóit, és a következőképpen írható fel: $f$

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

vagy:

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

[17] .

Az algoritmus összetettsége

Az algoritmus összetettsége a matematikai műveletek [19] . Az algoritmus csak kis mezők esetén lesz hatékony. Ez annak köszönhető, hogy mindent felsorolni kell . $O(n^{3}+qkn)$ ${\displaystyle c\in \mathbb {F} _{q))$

Fejlesztések

Egyszerű mező esetén, ha az érték nagy, akkor az értékek iterálása sokáig tart. De lehet definiálni egy halmazt , amely nem triviális [20] . Ehhez meg kell találni a [21] eredő gyökét , amelyből a halmaz áll majd . $p$ $c\in {\mathbb {Z} /p\mathbb {Z} }$ $M$ $c$ $\gcd(f(x),h(x)-c)$ $R(c)$ $M$
Egy több irreducibilis tényezővel nem rendelkező unitárius polinom felosztásának egy másik módszere a Berlekamp-algoritmus segítségével hatékonyan kiszámítható A mátrix átlós alakra való redukálásán alapul [22] . Maga a diagonalizáció folyamata azonban meglehetősen bonyolult. $f(x)\in GF(q)[x]$
Kaltofen és Lobo [23] a Berlekamp-algoritmus valószínűségi változatát javasolta, amely lehetővé teszi egy fokszámú polinom faktorizálását az aritmetikai műveletekben. A Kaltofen-Lobo algoritmust számítógépen valósították meg, és hatékonynak bizonyult nagyfokú polinomoknál, például az 10001 fokú polinomoknál körülbelül 102,5 órán keresztül működik egy mezőn egy Sun-4 számítógépen . $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}$

Alkalmazás

A polinomiális faktorizációs algoritmusok fontosak a kódoláselméletben és a véges mezők lineáris ismétlődési összefüggéseinek vizsgálatában. A Berlekamp-algoritmust arra is használják, hogy kiszámítsák a racionális számok mezője feletti egyenlet Galois-csoportját, és terepmegoldásokat készítsenek, polinomokat bővítsenek az egész számok gyűrűjére, hogy megtalálják az egyszerű racionális számok dekompozícióját az algebrai számok területén, és néhány más számítási probléma esetén [24] . Tényezőbázisú algoritmusokpolinomiális faktorizációs algoritmusok segítségével oldja meg a diszkrét logaritmus megtalálásának problémáját [25] , amelynek számítási bonyolultságára az ElGamal- séma épül .

Implementációk számítógépes algebrai rendszerekben

A PARI/GP számítógépes algebra rendszerben a Berlekamp-algoritmus a factormod[26] paranccsal használható .

Jegyzetek

↑ Berlekamp, 1967 , p. 1854: "A ciklikus kódokról".
↑ 1 2 Berlekamp, 1967 .
↑ Berlekamp, 1967 , p. 1853.
↑ Golomb, Solomon Wolf. Shift Register Sequences . — Aegean Park Pr; Átdolgozott kiadás, 1981. - 274 p. — ISBN 978-0894120480 .
↑ PETR K. Uber die Reduzibilitat eines Polynoms mit ganzzahligen Koeffi-zienten nach einem Primzahlmodul. — Casopis Pest Mat. Fys, 1937, 85-94 .
↑ Butler, MCR A polinomok véges mező feletti redukálhatóságáról. - The Quarterly Journal of Mathematics Oxford Second Series 5, 1954. - S. 102-107 .
↑ Schwarz, St. A polinomok véges mező feletti redukálhatóságáról. — Quart. J Math. Oxford Ser. (2) 7, 1956. - 110-124 .
↑ Lidl, 1988 , Történelmi kommentár, p. 223-224.
↑ Cantor DG, Zassenhaus H. Új algoritmus polinomok faktorálására véges mezőkön. — Matek. Comp., 1981. Vol. 36. - P. 587-592.
↑ von zur Gathen J., Shoup V. Frobenius-térképek és faktorálási polinomok számítása. — Számítógép. Complexity, 1992. - 2. kötet . - S. 187-224 .
↑ Vasilenko, 2003 , p. 185: "A Cantor-Zassenhaus algoritmus összetettsége".
↑ Lidl, 1988 , Problémanyilatkozat, p. 187.
↑ Vasilenko, 2003 , Definíciók, p. 172.
↑ 1 2 Vasilenko, 2003 , Az algoritmus leírása, p. 173.
↑ 1 2 3 4 Lidl, 1988 , Az algoritmus leírása.
↑ 1 2 3 4 Lidl, 1988 , Kicsinyítés az alapügyre, p. 188.
↑ 1 2 3 4 5 Lidl, 1988 , Az algoritmus helyességének indoklása, p. 189-190.
↑ 1 2 Vasilenko, 2003 , p. 174.
↑ Vasilenko, 2003 , p. 174: "Az algoritmus összetettsége."
↑ Lidl, 1988 , Bővebben a módszerről, p. 201.
↑ Van der Waerden, 1976 , Az eredményről, p. 124.
↑ Lidl, 1988 , Bővebben a módszerről, p. 206.
↑ Kaltofen E, Lobo A. High-degree polinomok faktorálása a fekete doboz Berlekamp algoritmussal // Proceedings of the international symposium on Symbolic and algebraic compution (ISSAC '94). - N. Y .: ACM Press, 1994. - P. 90-98 . — ISBN 0-89791-638-7 . - doi : 10.1145/190347.190371 .
↑ Lidl, 1988 , Az algoritmus alkalmazása, p. 187.
↑ Vasilenko, 2003 , Tényezőalapú algoritmusok használatáról a diszkrét logaritmus-feladat megoldására, p. 137.
↑ GP/PARI függvények katalógusa: Aritmetikai függvények Archiválva : 2007. március 11.

Irodalom

Berlekamp, Elwyn R. Polinomok faktorálása véges mezők felett // Bell System Technical Journal. - 1967. - 1. évf. 46 . - P. 1853-1859 . BSTJ Később újra megjelent: Berlekamp, Elwyn R. Algebraic Coding Theory . - McGraw-Hill Education , 1968. - ISBN 0-89412-063-8 .
Vasilenko O. N. Számelméleti algoritmusok a kriptográfiában . - M. : MTSNMO, 2003. - 328 p. — ISBN 5-94057-103-4 .
Lidl R. , Niederreiter G. Véges mezők = Finite Fields / Szerk. V. I. Nechaev. - 1. kiadás - M . : Mir, 1988. - T. 1. - 430 p. — ISBN 5-03-000065-8 .
Van der Waerden B.L. Algebra . — M.: Nauka, 1976. — 646 p. Archivált: 2013. november 2. aWayback Machine