Berlekamps algoritme

Berlekamps algoritme er en algoritme designet til at faktorisere unitære polynomier over et begrænset felt . Designet af Alvin Berlekamp i 1967 . Det kan også bruges til at teste irreducerbarheden af polynomier over endelige felter . Hovedideen med algoritmen er muligheden for at repræsentere det oprindelige polynomium som et produkt af de største fælles divisorer af selve polynomiet og nogle polynomier, der udvider sig op til en fri term. $f$

Berlekamps algoritme har en høj beregningsmæssig kompleksitet, så der er udviklet en række yderligere metoder til at reducere antallet af nødvendige matematiske operationer. På trods af dens kompleksitet er Berlekamps algoritme blevet implementeret i computeralgebrasystemer. Algoritmen har fundet bred anvendelse i kodningsteori og i studiet af lineære gentagelsesrelationer i endelige felter. Der er mange beregningsmæssige problemer i algebra og talteori, der på en eller anden måde er relateret til nedbrydningen af polynomier over endelige felter, for eksempel faktorisering af polynomier over ringen af heltal , finde nedbrydningen af et rationelt primtal i feltet af algebraiske tal, beregning Galois-gruppen af en eller anden ligning over feltet af rationelle tal og konstruktionen af feltudvidelser.

Oprettelseshistorie

En amerikansk matematiker, professor ved University of California, Berlekamp, studerede cykliske fejldetekterings- og korrektionskoder , herunder Bose-Chowdhury-Hockwingham-koden , hvis egenskaber afhænger af divisorerne for de genererende polynomier. Berlekamps tekniske fremskridt inden for afkodning af disse koder har gjort dem mere praktiske [1] .

Algoritmen blev først beskrevet i artiklen "Factoring Polynomials Over Finite Fields" [2] og senere gengivet i bogen "Algebraic Coding Theory" [2] . I dette papir fra 1967 [3] skriver Berlekamp, at faktoriseringsproblemet opstår i Golombs skrifter [ 4] . Imidlertid blev muligheden for at bruge en matrix til at bestemme antallet af normaliserede faktorer i et polynomium først bemærket i en artikel af Karel Piotr $B$ $f(x)$ [5] . Butlers artikel [6] fandt, at rangeringen af en matrixer, et andet bevis på dette faktum blev givet af Schwartz [7] . $VÆRE$ $nk$

Berlekamp-algoritmen blev nævnt i mange værker [8] og var den vigtigste algoritme til løsning af faktoriseringsproblemet indtil fremkomsten af Cantor-Zassenhaus-algoritmen i 1981[9] . Der blev udviklet en teknik [10] , der gør det muligt at faktorisere et polynomium ihvor er en indikator til at estimere kompleksiteten af at multiplicere kvadratmatricer [11] . $O(n^{{(\omega +1)/2+o(1)}}+n^{{1+o(1)}}\log q),$ $\omega$

Udsagn og definitioner

Problemet med faktorisering af et polynomium af grad ( ) over et begrænset felt ( , er et primtal ) [12] til forskellige irreducerbare unitære polynomier betragtes . $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}}}$

Til brug i algoritmen er en matrix bygget i henhold til følgende betingelser: $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}}

Et polynomium sådan, at , kaldes -nedbrydende polynomium [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$

Grundlæggende sag

Faktoriseringsalgoritme over et endeligt felt af et polynomium af formen: $\mathbb {F} _{q}$

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

består af følgende trin:

Matrixberegning [14] . $B$
Søg efter grundlaget for underrummet af løsninger af systemet af lineære ligninger [15] : $\overline {e_{1}},\dots ,\overline {e_{k}}$ $(B-E_{n})^{T}\mathbf {x} =\mathbf {0}$ , i dette tilfælde er det muligt at vælge vektoren , da den altid vil være til stede [15] i grundlaget for løsningsrummet på grund af det faktum, at kl . $\overline {e_{1}}=(1,\;0,\;....\;,\;0)$ $x^{iq}\equiv 1{\pmod {f(x)))$ $i=0$
Det fundne tal er antallet af irreducerbare divisorer [14] . $k$ $f(x)$
- Hvis , så er polynomiet
irreducerbart . $k=1$
Hvis , så har vektorerne formen . Disse tal bruges til at konstruere -dekomponerende polynomier: $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.$ .
Nedbrydningssøgning [15] : $f(x)=\prod _{{c\in {\mathbb {F}}_{q},}}\gcd(f(x),h_{2}(x)-c)$ som: $f(x)=\prod _{m}g_{{m,\;2}}(x)$ , hvor , i det generelle tilfælde, ikke er irreducerbare. Funktioner faktoriseres på samme måde [15] , dvs. $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}$ .

Generel sag

Problemet med faktorisering af et arbitrært unitært polynomium er reduceret til overvejelsen af hovedtilfældet. Til dette beregnes polynomiet

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

ved hjælp af Euklids algoritme .

Hvis så polynomiet ikke indeholder multiple rødder, da multipelroden også er roden af den afledede [16] . $d(x)=1,$
Hvis så betyder Hvis så for det er nødvendigt at udføre den beskrevne procedure indtil udvidelsen er opnået Polynomiet opfylder kravene i hovedtilfældet [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)$
Ellers er polynomiet en ikke-trivial divisor af polynomiet . Til gengæld har polynomiet ingen flere irreducerbare faktorer [16] . Hvis den indeholder flere faktorer, anvendes den beskrevne procedure også på den. Når du kender disse udvidelser, er det nemt at opnå udvidelsen . $d(x)$ $f(x)$ ${\frac {f(x)}{d(x)))$ $d(x)$ $f(x)$

Således er problemet med at faktorisere et vilkårligt unitært polynomium over et endeligt felt reduceret til at faktorisere et endeligt antal polynomier, der ikke har flere irreducerbare faktorer, det vil sige til hovedtilfældet [16] . $\mathbb {F} _{q}[x]$

Begrundelse

Lade:

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

, hvor .

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

Ifølge den kinesiske restsætning er der et unikt polynomium for ethvert sæt feltelementer [17] : $(c_{1},\;...,\;c_{k})$ $\mathbb {F} _{q}$

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

sådan at:

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

Polynomiet opfylder betingelsen [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}

og så [18] :

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

Fra tilstanden:

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

og det følger af, at faktorerne på højre side er coprime, at hver irreducibel divisor af polynomiet deler en og kun en af polynomierne . Således er gyldigheden og unikheden af nedbrydningen [18] bevist : $f(x)$ $h(x)-c$

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

Sådan finder du et polynomium:

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

Lad os se på sammenligningen:

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

hvilket svarer til betingelsen [17] :

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

Ved definitionen af matricen får vi: $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}

så [17] :

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

Det resulterende ligningssystem bestemmer koefficienterne for -nedbrydende polynomier og kan skrives som: $f$

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

eller:

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

[17] .

Algoritmens kompleksitet

Algoritmens kompleksitet er matematiske operationer [19] . Algoritmen vil kun være effektiv for små felter. Dette skyldes behovet for at opregne alle . $O(n^{3}+qkn)$ ${\displaystyle c\in \mathbb {F} _{q))$

Forbedringer

I tilfælde af et simpelt felt, hvis værdien er stor, vil det tage lang tid at gentage værdierne . Det er dog muligt at definere et sæt bestående af , som er ikke-trivielt [20] . For at gøre dette er det nødvendigt at finde rødderne af resultanten [21] , som vil udgøre sættet . $s$ $c\in {\mathbb {Z} /p\mathbb {Z} }$ $M$ $c$ $\gcd(f(x),h(x)-c)$ $R(c)$ $M$
En anden metode til nedbrydning af et enhedspolynomium , som ikke har flere irreducerbare faktorer, er baseret på at reducere en eller anden matrix A, der effektivt kan beregnes ved hjælp af Berlekamp-algoritmen, til en diagonal form [22] . Selve diagonaliseringsprocessen er dog ret kompliceret. $f(x)\i GF(q)[x]$
Kaltofen og Lobo [23] foreslog en probabilistisk version af Berlekamps algoritme, som gør det muligt at faktorisere et gradspolynomium i aritmetiske operationer. Kaltofen-Lobo-algoritmen blev implementeret på en computer og viste sig at være effektiv for højgradspolynomier, for eksempel for polynomier af grad 10001 , den virker på et felt i omkring 102,5 timer på en Sun-4- computer . $f(x)\i GF(q)[x]$ $n$ $O((n\log n+\log q)\cdot n(\log n)\log(\log n))$ $\mathbb {Z} /127\mathbb {Z}$

Ansøgning

Polynomielle faktoriseringsalgoritmer er vigtige for kodningsteori og for studiet af lineære gentagelsesrelationer i endelige felter. Berlekamp-algoritmen bruges også til at beregne Galois-gruppen af en ligning over feltet af rationelle tal og konstruere feltløsninger, udvide polynomier over ringen af heltal, for at finde dekomponeringen af et simpelt rationelt tal i feltet af algebraiske tal, og for nogle andre beregningsproblemer [24] . Algoritmer med faktorbaserbruge polynomielle faktoriseringsalgoritmer til at løse problemet med at finde en diskret logaritme [25] , på hvis beregningsmæssige kompleksitet, ElGamal- skemaet er bygget .

Implementeringer i computeralgebrasystemer

I PARI/GP computeralgebrasystemet kan Berlekamps algoritme bruges med kommandoen factormod[26] .

Noter

↑ Berlekamp, 1967 , s. 1854: "Om cykliske koder".
↑ 1 2 Berlekamp, 1967 .
↑ Berlekamp, 1967 , s. 1853.
↑ Golomb, Solomon Wolf. Skiftregistersekvenser . — Aegean Park Pr; Revideret udgave, 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 Om reducerbarheden af polynomier over et begrænset felt. - The Quarterly Journal of Mathematics Oxford Second Series 5, 1954. - S. 102-107 .
↑ Schwarz, St. Om polynomiers reduktion i et begrænset felt. — Kvart. J Math. Oxford Ser. (2) 7, 1956. - s. 110-124 .
↑ Lidl, 1988 , Historisk kommentar, s. 223-224.
↑ Cantor DG, Zassenhaus H. En ny algoritme til faktorisering af polynomier over endelige felter. — Matematik. Comp., 1981. Vol. 36. - S. 587-592.
↑ von zur Gathen J., Shoup V. Computing Frobenius maps and factoring polynomials. - Computer. Complexity, 1992. - Vol. 2 . - S. 187-224 .
↑ Vasilenko, 2003 , s. 185: "Kompleksiteten af Cantor-Zassenhaus-algoritmen".
↑ Lidl, 1988 , Problemformulering, s. 187.
↑ Vasilenko, 2003 , Definitioner, s. 172.
↑ 1 2 Vasilenko, 2003 , Beskrivelse af algoritmen, s. 173.
↑ 1 2 3 4 Lidl, 1988 , Beskrivelse af algoritmen.
↑ 1 2 3 4 Lidl, 1988 , Reduktion til hovedsagen, s. 188.
↑ 1 2 3 4 5 Lidl, 1988 , Begrundelse for algoritmens rigtighed, s. 189-190.
↑ 1 2 Vasilenko, 2003 , s. 174.
↑ Vasilenko, 2003 , s. 174: "Algorithmens kompleksitet."
↑ Lidl, 1988 , Mere om metoden, s. 201.
↑ Van der Waerden, 1976 , Om resultatet, s. 124.
↑ Lidl, 1988 , Mere om metoden, s. 206.
↑ Kaltofen E, Lobo A. Factoring high-grade polynomials by the black box Berlekamp algoritme // Proceedings of the international symposium on Symbolic and algebraic computation (ISSAC '94). - N. Y .: ACM Press, 1994. - S. 90-98 . — ISBN 0-89791-638-7 . - doi : 10.1145/190347.190371 .
↑ Lidl, 1988 , Application of the Algorithm, s. 187.
↑ Vasilenko, 2003 , Om brugen af algoritmer med faktorbaser til løsning af det diskrete logaritmeproblem, s. 137.
↑ Katalog over GP/PARI-funktioner: Aritmetiske funktioner Arkiveret 11. marts 2007.

Litteratur

Berlekamp, Elwyn R. Factoring Polynomials Over Finite Fields // Bell System Technical Journal. - 1967. - Bd. 46 . - S. 1853-1859 . BSTJ Senere genudgivet i: Berlekamp, Elwyn R. Algebraic Coding Theory . - McGraw-Hill Education , 1968. - ISBN 0-89412-063-8 .
Vasilenko O. N. Talteoretiske algoritmer i kryptografi . - M. : MTSNMO, 2003. - 328 s. — ISBN 5-94057-103-4 .
Lidl R. , Niederreiter G. Finite Fields = Finite Fields / Ed. V. I. Nechaev. - 1. udg. - M . : Mir, 1988. - T. 1. - 430 s. — ISBN 5-03-000065-8 .
Van der Waerden B.L. Algebra . — M.: Nauka, 1976. — 646 s. Arkiveret2. november 2013 påWayback Machine