Berlekamps algoritm

Berlekamps algoritm är en algoritm utformad för att faktorisera enhetliga polynom över ett ändligt fält . Designad av Alvin Berlekamp 1967 . Den kan också användas för att testa irreducerbarheten av polynom över ändliga fält . Algoritmens huvudidé är möjligheten att representera det ursprungliga polynomet som en produkt av de största gemensamma divisorerna för själva polynomet och några polynom som expanderar upp till en fri term. $f$

Berlekamps algoritm har en hög beräkningskomplexitet, så ett antal ytterligare metoder har utvecklats för att minska antalet nödvändiga matematiska operationer. Men trots sin komplexitet har Berlekamps algoritm implementerats i datoralgebrasystem. Algoritmen har funnit bred tillämpning inom kodningsteori och i studiet av linjära återfallsrelationer i finita fält. Det finns många beräkningsproblem inom algebra och talteori som på något sätt är relaterade till sönderdelningen av polynom över ändliga fält, till exempel faktorisering av polynom över ringen av heltal , hitta sönderdelningen av ett rationellt primtal i fältet för algebraiska tal, beräkning Galois-gruppen av någon ekvation över fältet av rationella tal och konstruktionen av fältförlängningar.

Skapande historia

En amerikansk matematiker, professor vid University of California, Berlekamp, studerade cykliska feldetekterings- och korrigeringskoder , inklusive Bose-Chowdhury-Hockwingham-koden , vars egenskaper beror på divisorerna för de genererande polynomen. Berlekamps tekniska framsteg när det gäller att avkoda dessa koder har gjort dem mer praktiska [1] .

Algoritmen beskrevs först i artikeln "Factoring Polynomials Over Finite Fields" [2] och återgavs senare i boken "Algebraic Coding Theory" [2] . I denna uppsats från 1967 [3] skriver Berlekamp att faktoriseringsproblemet uppstår i Golombs skrifter [ 4] . Möjligheten att använda en matris för att bestämma antalet normaliserade faktorer för ett polynom uppmärksammades först i en artikel av Karel Piotr $B$ $f(x)$ [5] . Butlers artikel [6] fann att rangordningen för en matrisär, ett annat bevis för detta faktum gavs av Schwartz [7] . $VARA$ $nk$

Berlekamp-algoritmen nämndes i många verk [8] och var den huvudsakliga algoritmen för att lösa faktoriseringsproblemet fram till tillkomsten av Cantor-Zassenhaus-algoritmen 1981[9] . En teknik utvecklades [10] som tillåter faktorisering av ett polynomdär är en indikator för att uppskatta komplexiteten av att multiplicera kvadratmatriser [11] . $O(n^{{(\omega +1)/2+o(1)}}+n^{{1+o(1)}}\log q),$ $\omega$

Påstående och definitioner

Problemet med faktorisering av ett polynom av grad ( ) över ett ändligt fält ( , är ett primtal ) [12] till olika irreducible unitary polynoms anses . $f(x)$ $n$ $n\geq 2$ $\mathbb {F} _{q}$ $q=p^{m}$ $sid$ $f(x)=f_{1}(x)^{{e_{1}}}\cdots f_{k}(x)^{{e_{k}}}$

För användning i algoritmen byggs en matris enligt följande villkor: $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}}

Ett polynom sådant att , kallas -nedbrytande 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$

Grundläggande fall

Faktoriseringsalgoritm över ett ändligt fält av ett polynom av formen: $\mathbb {F} _{q}$

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

består av följande steg:

Matrisberäkning [14] . $B$
Sök efter grunden för underrummet av lösningar av systemet av linjära ekvationer [15] : $\overline {e_{1}},\dots ,\overline {e_{k}}$ $(B-E_{n})^{T}\mathbf {x} =\mathbf {0}$ , i detta fall är det möjligt att välja vektorn , eftersom den alltid kommer att finnas [15] i basen av lösningsutrymmet på grund av det faktum att vid . $\overline {e_{1}}=(1,\;0,\;....\;,\;0)$ $x^{iq}\equiv 1{\pmod {f(x)))$ $i=0$
Det hittade numret är antalet irreducerbara divisorer [14] . $k$ $f(x)$
- Om , då är polynomet
irreducerbart . $k=1$
Om , då har vektorerna formen . Dessa tal används för att konstruera -nedbrytande polynom: $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.$ .
Nedbrytningssökning [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)$ , där , i det allmänna fallet, inte är irreducerbara. Funktioner faktoriseras på samma sätt [15] , dvs. $g_{{m,\;s}}(x),\quad s=\överlinje {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=\överlinje {2,k-1}$ .

Allmänt fall

Problemet med faktorisering av ett godtyckligt enhetligt polynom reduceras till övervägandet av huvudfallet. För detta beräknas polynomet

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

med Euklids algoritm .

Om då polynomet inte innehåller flera rötter, eftersom multipelroten också är roten till derivatan [16] . $d(x)=1,$
Om betyder då Om då för det är nödvändigt att göra den beskrivna proceduren tills expansionen erhålls . Polynomet uppfyller kraven i huvudfallet [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)$
Annars är polynomet en icke-trivial divisor av polynomet . I sin tur har polynomet inga multipla irreducerbara faktorer [16] . Om den innehåller flera faktorer, tillämpas även den beskrivna proceduren på den. Genom att känna till dessa expansioner är det lätt att få expansionen . $d(x)$ $f(x)$ ${\frac {f(x)}{d(x)))$ $d(x)$ $f(x)$

Således reduceras problemet med att faktorisera ett godtyckligt enhetligt polynom över ett ändligt fält till att faktorisera ett ändligt antal polynom som inte har flera irreducerbara faktorer, det vill säga till huvudfallet [16] . $\mathbb {F} _{q}[x]$

Motivering

Låta:

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

, var .

\quad e_{i}=1,\quad i=\överlinje {1,k}

Enligt den kinesiska restsatsen finns det ett unikt polynom för vilken uppsättning fältelement som helst [ 17] : $(c_{1},\;...,\;c_{k})$ $\mathbb {F} _{q}$

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

Så att:

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

Polynomet uppfyller villkoret [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}

och så [18] :

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

Från villkoret:

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

och det följer av det faktum att faktorerna på höger sida är coprime att varje irreducible divisor av polynomet delar en och endast en av polynomen . Således bevisas giltigheten och unikheten av nedbrytningen [18] : $f(x)$ $h(x)-c$

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

Så här hittar du ett polynom:

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

Låt oss titta på jämförelsen:

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

vilket motsvarar villkoret [17] :

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

Genom definitionen av matrisen får vi: $B$

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

alltså [17] :

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

Det resulterande ekvationssystemet bestämmer koefficienterna för -nedbrytande polynom och kan skrivas 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 komplexitet

Algoritmens komplexitet är matematiska operationer [19] . Algoritmen kommer endast att vara effektiv för små fält. Detta beror på behovet av att räkna upp alla . $O(n^{3}+qkn)$ ${\displaystyle c\in \mathbb {F} _{q))$

Förbättringar

I fallet med ett enkelt fält, om värdet är stort, kommer det att ta lång tid att iterera över värdena . Det är dock möjligt att definiera en uppsättning som består av som är icke-trivial [20] . För att göra detta är det nödvändigt att hitta rötterna till den resulterande [21] , som kommer att utgöra uppsättningen . $sid$ $c\in {\mathbb {Z} /p\mathbb {Z} }$ $M$ $c$ $\gcd(f(x),h(x)-c)$ $R(c)$ $M$
En annan metod för nedbrytning av ett enhetligt polynom , som inte har flera irreducerbara faktorer, är baserad på att reducera någon matris A som är effektivt beräkningsbar med Berlekamp-algoritmen till en diagonal form [22] . Själva diagonaliseringsprocessen är dock ganska komplicerad. $f(x)\i GF(q)[x]$
Kaltofen och Lobo [23] föreslog en probabilistisk version av Berlekamps algoritm, som gör det möjligt att faktorisera ett gradpolynom i aritmetiska operationer. Kaltofen-Lobo-algoritmen implementerades på en dator och visade sig vara effektiv för höggradspolynom, till exempel för polynom med grad 10001 , den fungerar på ett fält i cirka 102,5 timmar på en Sun-4- dator . $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}$

Applikation

Polynomfaktoriseringsalgoritmer är viktiga för kodningsteori och för studiet av linjära återfallsrelationer i finita fält. Berlekamp-algoritmen används också för att beräkna Galois-gruppen för en ekvation över fältet av rationella tal och konstruera fältlösningar, expandera polynom över ringen av heltal, för att hitta nedbrytningen av ett enkelt rationellt tal i fältet för algebraiska tal, och för vissa andra beräkningsproblem [24] . Algoritmer med faktorbaseranvänd polynomfaktoriseringsalgoritmer för att lösa problemet med att hitta en diskret logaritm [25] , på vars beräkningskomplexitet, ElGamal- schemat är byggt .

Implementeringar i datoralgebrasystem

I PARI/GP datoralgebrasystem kan Berlekamps algoritm användas med kommandot factormod[26] .

Anteckningar

↑ Berlekamp, 1967 , sid. 1854: "Om cykliska koder".
↑ 1 2 Berlekamp, 1967 .
↑ Berlekamp, 1967 , sid. 1853.
↑ Golomb, Solomon Wolf. Skiftregistersekvenser . — Aegean Park Pr; Reviderad upplaga, 1981. - 274 sid. — 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 polynomens reducerbarhet över ett ändligt fält. - The Quarterly Journal of Mathematics Oxford Second Series 5, 1954. - S. 102-107 .
↑ Schwarz, St. Om polynoms reducerbarhet över ett ﬁnit fält. — Quart. J Math. Oxford Ser. (2) 7, 1956. - s. 110-124 .
↑ Lidl, 1988 , Historisk kommentar, sid. 223-224.
↑ Cantor DG, Zassenhaus H. En ny algoritm för faktorisering av polynom över ändliga fält. — Matematik. Comp., 1981. Vol. 36. - P. 587-592.
↑ von zur Gathen J., Shoup V. Computing Frobenius maps and factoring polynomials. - Dator. Complexity, 1992. - Vol 2 . - S. 187-224 .
↑ Vasilenko, 2003 , sid. 185: "Komplexiteten i Cantor-Zassenhaus-algoritmen".
↑ Lidl, 1988 , Redogörelse av problemet, sid. 187.
↑ Vasilenko, 2003 , Definitioner, sid. 172.
↑ 1 2 Vasilenko, 2003 , Beskrivning av algoritmen, sid. 173.
↑ 1 2 3 4 Lidl, 1988 , Beskrivning av algoritmen.
↑ 1 2 3 4 Lidl, 1988 , Reduktion till huvudmålet, sid. 188.
↑ 1 2 3 4 5 Lidl, 1988 , Motivering av algoritmens riktighet, sid. 189-190.
↑ 1 2 Vasilenko, 2003 , sid. 174.
↑ Vasilenko, 2003 , sid. 174: "Algorithmens komplexitet."
↑ Lidl, 1988 , Mer om metoden, sid. 201.
↑ Van der Waerden, 1976 , Om resultatet, sid. 124.
↑ Lidl, 1988 , Mer om metoden, sid. 206.
↑ Kaltofen E, Lobo A. Factoring high-grade polynomials by the black box Berlekamp algorithm // 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 , Application of the Algorithm, sid. 187.
↑ Vasilenko, 2003 , Om användningen av algoritmer med faktorbaser för att lösa det diskreta logaritmproblemet, sid. 137.
↑ Katalog över GP/PARI-funktioner: Aritmetiska funktioner Arkiverad 11 mars 2007.

Litteratur

Berlekamp, Elwyn R. Faktorering av polynom över ändliga fält // Bell System Technical Journal. - 1967. - Vol. 46 . - P. 1853-1859 . BSTJ Senare återpublicerad i: Berlekamp, Elwyn R. Algebraic Coding Theory . - McGraw-Hill Education , 1968. - ISBN 0-89412-063-8 .
Vasilenko O. N. Talteoretiska algoritmer i kryptografi . - M. : MTSNMO, 2003. - 328 sid. — ISBN 5-94057-103-4 .
Lidl R. , Niederreiter G. Finita Fields = Finita Fields / Ed. V. I. Nechaev. - 1:a uppl. - M . : Mir, 1988. - T. 1. - 430 sid. — ISBN 5-03-000065-8 .
Van der Waerden B.L. Algebra . — M.: Nauka, 1976. — 646 sid. Arkiverad2 november 2013 påWayback Machine