Berlekampin algoritmi

Berlekampin algoritmi on algoritmi, joka on suunniteltu jakamaan unitaarisia polynomeja rajallisen kentän yli . Alvin Berlekampin suunnittelema vuonna 1967 . Sitä voidaan käyttää myös polynomien redusoitumattomuuden testaamiseen äärellisten kenttien yli . Algoritmin pääideana on mahdollisuus esittää alkuperäinen polynomi itse polynomin ja joidenkin vapaaseen termiin laajenevien polynomien suurimpien yhteisten jakajien tulona. $f$

Berlekampin algoritmilla on suuri laskennallinen monimutkaisuus, joten tarvittavien matemaattisten operaatioiden määrän vähentämiseksi on kehitetty useita lisämenetelmiä. Monimutkaisuudestaan huolimatta Berlekampin algoritmi on kuitenkin toteutettu tietokonealgebrajärjestelmissä. Algoritmi on löytänyt laajan käytön koodausteoriassa ja äärellisten kenttien lineaaristen toistuvuussuhteiden tutkimuksessa. Algebrassa ja lukuteoriassa on monia laskentaongelmia, jotka liittyvät jollain tapaa polynomien hajoamiseen äärellisten kenttien yli, esimerkiksi polynomien laskeminen kokonaislukujen renkaan yli, alkurationaaliluvun hajotuksen löytäminen algebrallisten lukujen kentässä, laskeminen joidenkin yhtälöiden Galois-ryhmä rationaalisten lukujen alalla ja kenttälaajennusten rakentamisessa.

Luontihistoria

Amerikkalainen matemaatikko, professori Kalifornian yliopistossa Berlekampissa, tutki syklisiä virheiden havaitsemis- ja korjauskoodeja , mukaan lukien Bose-Chowdhury-Hockwingham-koodia , jonka ominaisuudet riippuvat generoivien polynomien jakajista. Berlekampin tekninen kehitys näiden koodien purkamisessa on tehnyt niistä käytännöllisempiä [1] .

Algoritmi kuvattiin ensin artikkelissa "Factoring Polynomials Over Fields" [2] ja myöhemmin toistettiin kirjassa "Algebraic Coding Theory" [2] . Tässä vuoden 1967 artikkelissa [3] Berlekamp kirjoittaa, että faktorointiongelma nousee esiin Golombin kirjoituksissa [ 4] . Kuitenkin mahdollisuus käyttää matriisia polynomin normalisoitujen tekijöiden lukumäärän määrittämiseen havaittiin ensimmäisen kerran Karel Piotrin artikkelissa. $B$ $f(x)$ [5] . Butlerin artikkelissa [6] havaittiin, että matriisin arvoon, toisen todisteen tästä tosiasiasta antoi Schwartz [7] . $OLLA$ $nk$

Berlekamp-algoritmi mainittiin monissa teoksissa [8] ja se oli pääalgoritmi faktorointiongelman ratkaisemisessa Cantor-Zassenhaus-algoritmin käyttöön asti vuonna 1981.[9] . Kehitettiin tekniikka [10] , joka mahdollistaa polynominmissä on indikaattori neliömatriisien kertomisen monimutkaisuuden arvioinnissa [11] . $O(n^{{(\omega +1)/2+o(1)}}+n^{{1+o(1)}}\log q,$ $\omega$

Lausunto ja määritelmät

Tarkastellaan ongelmaa asteisen ( ) polynomin faktorisoinnista äärellisessä kentässä ( , on alkuluku ) [12] erilaisiksi pelkistymättömiksi unitaarisiksi polynomeiksi . $f(x)$ $n$ $n\geq 2$ $\mathbb {F} _{q}$ $q=p^{m}$ $s$ $f(x)=f_{1}(x)^{{e_{1}}}\cdots f_{k}(x)^{{e_{k}}}$

Algoritmissa käytettäväksi matriisi rakennetaan seuraavien ehtojen mukaisesti: $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}}

Sellaista polynomia , että , kutsutaan -hajoavaksi polynomiksi [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$

Perustapaus

Faktorisointialgoritmi muotoa olevan polynomin äärellisessä kentässä : $\mathbb {F} _{q}$

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

koostuu seuraavista vaiheista:

Matriisilaskenta [14] . $B$
Etsi lineaariyhtälöjärjestelmän [15] ratkaisujen aliavaruuden perusta : $\overline {e_{1}},\dots ,\overline {e_{k}}$ $(B-E_{n})^{T}\mathbf {x} =\mathbf {0}$ , tässä tapauksessa on mahdollista valita vektori , koska se on aina läsnä [15] ratkaisuavaruuden perusteella johtuen siitä, että klo . $\overline {e_{1}}=(1,\;0,\;....\;,\;0)$ $x^{iq}\equiv 1{\pmod {f(x)))$ $i = 0$
Löytynyt luku on redusoitumattomien jakajien lukumäärä [14] . $k$ $f(x)$
- Jos , niin polynomi on
redusoitumaton . $k = 1$
Jos , niin vektoreilla on muoto . Näitä lukuja käytetään hajottavien polynomien muodostamiseen: $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.$ .
Hajotushaku [15] : $f(x)=\prod _{{c\in {\mathbb {F}}_{q},}}\gcd(f(x),h_{2}(x)-c)$ kuten: $f(x)=\tuote _{m}g_{{m,\;2}}(x)$ , joissa , eivät yleensä ole redusoitumattomia. Funktiot faktoroidaan samalla tavalla [15] , eli: $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}$ .

Yleinen tapaus

Mielivaltaisen unitaarisen polynomin tekijöiden jakamisen ongelma rajoittuu päätapauksen tarkasteluun. Tätä varten lasketaan polynomi

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

käyttämällä Euclid-algoritmia .

Jos sitten polynomi ei sisällä useita juuria, koska monijuuri on myös derivaatan juuri [16] . $d(x)=1,$
Jos sitten tarkoittaa If , niin sillä on välttämätöntä tehdä kuvattu toimenpide, kunnes laajennus saadaan . Polynomi täyttää päätapauksen vaatimukset [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)$
Muuten polynomi on polynomin ei-triviaali jakaja . Polynomilla ei puolestaan ole useita redusoitumattomia tekijöitä [16] . Jos se sisältää useita tekijöitä, kuvattua menettelyä sovelletaan myös siihen. Kun tiedät nämä laajennukset, on helppo hankkia laajennus . $d(x)$ $f(x)$ ${\frac {f(x)}{d(x)))$ $d(x)$ $f(x)$

Täten ongelma mielivaltaisen unitaaripolynomin tekijöiden määrittämisessä äärellisen kentän yli rajoittuu äärellisen määrän polynomeihin, joilla ei ole useita redusoitumattomia tekijöitä, eli päätapaukseen [16] . $\mathbb {F} _{q}[x]$

Perustelut

Päästää:

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

, missä .

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

Kiinan jäännöslauseen mukaan mille tahansa kenttäelementtijoukolle on ainutlaatuinen polynomi [17] : $(c_{1},\;...,\;c_{k})$ $\mathbb {F} _{q}$

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

sellainen että:

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

Polynomi täyttää ehdon [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}

ja niin [18] :

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

Tilanteesta:

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

ja siitä tosiasiasta, että oikean puolen tekijät ovat koprime, seuraa, että jokainen polynomin redusoitumaton jakaja jakaa yhden ja vain yhden polynomeista . Siten hajotuksen [18] pätevyys ja ainutlaatuisuus todistetaan : $f(x)$ $h(x)-c$

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

Polynomin etsiminen:

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

Katsotaanpa vertailua:

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

joka vastaa ehtoa [17] :

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

Matriisin määritelmän mukaan saamme: $B$

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

niin [17] :

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

Tuloksena oleva yhtälöjärjestelmä määrittää -hajoavien polynomien kertoimet ja voidaan kirjoittaa seuraavasti: $f$

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

tai:

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

[17] .

Algoritmin monimutkaisuus

Algoritmin monimutkaisuus on matemaattiset operaatiot [19] . Algoritmi toimii vain pienissä kentissä. Tämä johtuu tarpeesta luetella kaikki . $O(n^{3}+qkn)$ ${\displaystyle c\in \mathbb {F} _{q))$

Parannukset

Yksinkertaisen kentän tapauksessa, jos arvo on suuri, arvojen iterointi kestää kauan. On kuitenkin mahdollista määritellä joukko , joka koostuu ei- triviaalista [20] . Tätä varten on löydettävä resultantin [21] juuret , joka muodostaa joukon . $s$ $c\in {\mathbb {Z} /p\mathbb {Z} }$ $M$ $c$ $\gcd(f(x),h(x)-c)$ $R(c)$ $M$
Toinen menetelmä unitaaripolynomin hajottamiseksi , jolla ei ole useita redusoitumattomia tekijöitä, perustuu jonkin Berlekamp-algoritmin avulla tehokkaasti laskettavissa olevan matriisin A pelkistämiseen diagonaalimuotoon [22] . Itse diagonalisointiprosessi on kuitenkin melko monimutkainen. $f(x)\in GF(q)[x]$
Kaltofen ja Lobo [23] ehdottivat todennäköisyyspohjaista versiota Berlekampin algoritmista, joka mahdollistaa astepolynomin kertoimen aritmeettisissa operaatioissa . Kaltofen-Lobo-algoritmi toteutettiin tietokoneella ja osoittautui tehokkaaksi korkean asteen polynomeille, esimerkiksi asteen 10001 polynomeille se toimii kentällä noin 102,5 tuntia Sun-4- tietokoneella . $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}$

Sovellus

Polynomifaktorointialgoritmit ovat tärkeitä koodausteorialle ja lineaaristen toistuvuussuhteiden tutkimiseen äärellisissä kentissä. Berlekamp-algoritmia käytetään myös yhtälön Galois-ryhmän laskemiseen rationaalisten lukujen kentän yli ja kenttäratkaisujen muodostamiseen, polynomien laajentamiseen kokonaislukujen renkaan yli, yksinkertaisen rationaaliluvun hajotuksen löytämiseen algebrallisten lukujen kentässä, ja joihinkin muihin laskentaongelmiin [24] . Algoritmit tekijäperusteillakäyttää polynomifaktorointialgoritmeja ratkaistaksesi ongelman löytää diskreetti logaritmi [25] , jonka laskennallisen monimutkaisuuden varaan ElGamal- kaavio rakennetaan .

Toteutukset tietokonealgebrajärjestelmissä

PARI/GP tietokonealgebrajärjestelmässä Berlekampin algoritmia voidaan käyttää komennolla factormod[26] .

Muistiinpanot

↑ Berlekamp, 1967 , s. 1854: "syklisistä koodeista".
↑ 1 2 Berlekamp, 1967 .
↑ Berlekamp, 1967 , s. 1853.
↑ Golomb, Solomon Wolf. Vaihtorekisterisekvenssit . — Aegean Park Pr; Tarkistettu painos, 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, s. 85-94 .
↑ Butler, MCR Polynomien pelkistävyydestä äärellisessä kentässä. - The Quarterly Journal of Mathematics Oxford Second Series 5, 1954. - S. 102-107 .
↑ Schwarz, St. Polynomien pelkistävyydestä äärellisessä kentässä. — Quart. J Math. Oxford Ser. (2) 7, 1956. - s. 110-124 .
↑ Lidl, 1988 , Historiallinen kommentti, s. 223-224.
↑ Cantor DG, Zassenhaus H. Uusi algoritmi polynomien faktorointiin äärellisten kenttien yli. — Matematiikka. Comp., 1981. Voi. 36. - P. 587-592.
↑ von zur Gathen J., Shoup V. Frobenius-karttojen laskeminen ja tekijäpolynomien laskeminen. - Tietokone. Complexity, 1992. - Vol. 2 . - S. 187-224 .
↑ Vasilenko, 2003 , s. 185: "Cantor-Zassenhaus-algoritmin monimutkaisuus".
↑ Lidl, 1988 , Ongelman selvitys, s. 187.
↑ Vasilenko, 2003 , Määritelmät, s. 172.
↑ 1 2 Vasilenko, 2003 , Algoritmin kuvaus, s. 173.
↑ 1 2 3 4 Lidl, 1988 , Algoritmin kuvaus.
↑ 1 2 3 4 Lidl, 1988 , Alennus pääasiaan, s. 188.
↑ 1 2 3 4 5 Lidl, 1988 , Algoritmin oikeellisuuden perustelu, s. 189-190.
↑ 1 2 Vasilenko, 2003 , s. 174.
↑ Vasilenko, 2003 , s. 174: "Algoritmin monimutkaisuus."
↑ Lidl, 1988 , Lisää menetelmästä, s. 201.
↑ Van der Waerden, 1976 , On the Resultant, s. 124.
↑ Lidl, 1988 , Lisää menetelmästä, s. 206.
↑ Kaltofen E, Lobo A. Korkean asteen polynomien faktorointi black box Berlekamp -algoritmilla // Proceedings of the International Symposium on Symbolic and algebraic computation (ISSAC '94). - N. Y .: ACM Press, 1994. - P. 90-98 . — ISBN 0-89791-638-7 . - doi : 10.1145/190347.190371 .
↑ Lidl, 1988 , Algoritmin soveltaminen, s. 187.
↑ Vasilenko, 2003 , Tekijäpohjaisten algoritmien käytöstä diskreetin logaritmiongelman ratkaisemiseen, s. 137.
↑ GP/PARI-funktioiden luettelo: Aritmeettiset funktiot Arkistoitu 11. maaliskuuta 2007.

Kirjallisuus

Berlekamp, Elwyn R. Polynomien faktorointi äärellisten kenttien yli // Bell System Technical Journal. - 1967. - Voi. 46 . - P. 1853-1859 . BSTJ Myöhemmin julkaistu uudelleen: Berlekamp, Elwyn R. Algebraic Coding Theory . - McGraw-Hill Education , 1968. - ISBN 0-89412-063-8 .
Vasilenko O. N. Lukuteoreettiset algoritmit kryptografiassa . - M .: MTSNMO, 2003. - 328 s. — ISBN 5-94057-103-4 .
Lidl R. , Niederreiter G. Finite Fields = Finite Fields / Ed. V. I. Nechaev. - 1. painos - M . : Mir, 1988. - T. 1. - 430 s. — ISBN 5-03-000065-8 .
Van der Waerden B.L. Algebra . - M.: Nauka, 1976. - 646 s. Arkistoitu2. marraskuuta 2013Wayback Machinessa