Berlekampsův algoritmus - Berlekamps algorithm - Wikipedia

v matematika, zejména výpočetní algebra, Berlekampův algoritmus je dobře známá metoda pro faktoring polynomů nad konečnými poli (také známý jako Galoisova pole). Algoritmus se skládá hlavně z matice redukce a polynom GCD výpočty. To bylo vynalezeno Elwyn Berlekamp v roce 1967. Byl to dominantní algoritmus pro řešení problému až do Algoritmus Cantor – Zassenhaus z roku 1981. V současné době je implementován v mnoha známých systémy počítačové algebry.

Přehled

Berlekampův algoritmus bere jako vstup a polynom bez čtverců ${ displaystyle f (x)}$ (tj. bez opakujících se faktorů) stupně ${ displaystyle n}$ s koeficienty v konečném poli ${ displaystyle mathbb {F} _ {q}}$ a dává jako výstup polynom ${ displaystyle g (x)}$ s koeficienty ve stejné oblasti tak, že ${ displaystyle g (x)}$ rozděluje ${ displaystyle f (x)}$. Algoritmus lze poté použít rekurzivně na tyto a následující dělitele, dokud nenajdeme rozklad ${ displaystyle f (x)}$ do pravomocí neredukovatelné polynomy (připomínáme, že prsten polynomů nad konečným polem je a jedinečná faktorizační doména ).

Všechny možné faktory ${ displaystyle f (x)}$ jsou obsaženy v faktorový prsten

${ displaystyle R = { frac { mathbb {F} _ {q} [x]} { langle f (x) rangle}}.}$

Algoritmus se zaměřuje na polynomy ${ displaystyle g (x) v R}$ které uspokojují shodu:

${ displaystyle g (x) ^ {q} ekviv g (x) { pmod {f (x)}}. ,}$

Tyto polynomy tvoří a subalgebra z R (což lze považovat za ${ displaystyle n}$-dimenzionální vektorový prostor přes ${ displaystyle mathbb {F} _ {q}}$), nazvaný Berlekamp subalgebra. Berlekampova subalgebra je zajímavá, protože polynomy ${ displaystyle g (x)}$ obsahuje uspokojení

${ displaystyle f (x) = prod _ {s in mathbb {F} _ {q}} gcd (f (x), g (x) -s).}$

Obecně platí, že ne každý GCD ve výše uvedeném produktu bude netriviálním faktorem ${ displaystyle f (x)}$, ale některé poskytují faktory, které hledáme.

Berlekampův algoritmus najde polynomy ${ displaystyle g (x)}$ vhodné pro použití s ​​výše uvedeným výsledkem výpočtem základu pro Berlekampovu subalgebru. Toho je dosaženo pozorováním, že Berlekampova subalgebra je ve skutečnosti jádro jisté ${ displaystyle n krát n}$ matice skončila ${ displaystyle mathbb {F} _ {q}}$, který je odvozen z takzvané Berlekampovy matice polynomu, označený ${ displaystyle { mathcal {Q}}}$. Li ${ displaystyle { mathcal {Q}} = [q_ {i, j}]}$ pak ${ displaystyle q_ {i, j}}$ je koeficient ${ displaystyle j}$-tý mocninový termín při snižování ${ displaystyle x ^ {iq}}$ modulo ${ displaystyle f (x)}$, tj.:

${ displaystyle x ^ {iq} ekviv q_ {i, n-1} x ^ {n-1} + q_ {i, n-2} x ^ {n-2} + ldots + q_ {i, 0 } { pmod {f (x)}}. ,}$

S určitým polynomem ${ displaystyle g (x) v R}$, řekněme:

${ displaystyle g (x) = g_ {n-1} x ^ {n-1} + g_ {n-2} x ^ {n-2} + ldots + g_ {0}, ,}$

můžeme spojit vektor řádků:

${ displaystyle g = (g_ {0}, g_ {1}, ldots, g_ {n-1}). ,}$

Je relativně jednoduché vidět, že vektor řádků ${ displaystyle g { mathcal {Q}}}$ stejným způsobem odpovídá snížení o ${ displaystyle g (x) ^ {q}}$ modulo ${ displaystyle f (x)}$. V důsledku toho polynom ${ displaystyle g (x) v R}$ je v subalgebře Berlekamp právě tehdy ${ displaystyle g ({ mathcal {Q}} - I) = 0}$ (kde ${ displaystyle I}$ je ${ displaystyle n krát n}$ matice identity ), tj. právě tehdy, pokud je v prázdném prostoru ${ displaystyle { mathcal {Q}} - já}$.

Výpočtem matice ${ displaystyle { mathcal {Q}} - já}$ a redukovat to na snížená řada echelon forma a potom snadno odečteme základ pro prázdný prostor, můžeme najít základ pro Berlekampovu subalgebru, a tedy konstruovat polynomy ${ displaystyle g (x)}$ v tom. Poté musíme postupně vypočítat GCD výše uvedené formy, dokud nenajdeme netriviální faktor. Protože kruh polynomů nad polem je a Euklidovská doména, můžeme tyto GCD vypočítat pomocí Euklidovský algoritmus.

Konceptuální algebraické vysvětlení

S nějakou abstraktní algebrou se koncept Berlkemapova algoritmu stává koncepčně jasný. Představujeme konečné pole ${ textstyle mathbb {F} _ {q} [x]}$, kde ${ textstyle q = p ^ {m}}$ pro některé prime p, as ${ textstyle mathbb {F} _ {p} [y] / (g (y))}$. Můžeme to předpokládat ${ textstyle f (x) in mathbb {F} _ {q} [x]}$ je čtverec volný, přičemž vezmeme všechny možné pth kořeny a poté vypočítáme gcd s jeho derivací.

Předpokládejme to ${ textstyle f (x) = f_ {1} (x) ldots f_ {n} (x)}$ je faktorizace na neredukovatelné. Pak máme prstenový izomorfismus, ${ textstyle sigma: mathbb {F} _ {q} [x] / (f (x)) do prod _ {i} mathbb {F} _ {q} [x] / (f_ {i }(X))}$, daný čínskou větou o zbytku. Zásadní pozorování je, že Frobenius automorfismus ${ textový styl x až x ^ {p}}$ dojíždí s ${ textstyle sigma}$, takže pokud označíme ${ textstyle { text {Fix}} _ {p} (R) = {f v R: f ^ {p} = f }}$, pak ${ textstyle sigma}$ omezuje na izomorfismus ${ textstyle { text {Fix}} _ {p} ( mathbb {F} _ {q} [x] / (f (x))) to prod _ {i = 1} ^ {n} { text {Fix}} _ {p} ( mathbb {F} _ {q} [x] / (f_ {i} (x)))}$. Podle teorie konečných polí, ${ textstyle { text {Fix}} _ {p} ( mathbb {F} _ {q} [x] / (f_ {i} (x))}$ je vždy hlavním podpolem tohoto rozšíření pole. Tím pádem, ${ textstyle { text {Fix}} _ {p} ( mathbb {F} _ {q} [x] / (f (x)))}$ má ${ textový styl}$ prvky právě tehdy ${ textstyle f (x)}$ je neredukovatelný.

Navíc můžeme použít skutečnost, že Frobeniova automorfismus je ${ textstyle mathbb {F} _ {p}}$-lineární pro výpočet pevné sady. To znamená, že si toho všimneme ${ textstyle { text {Fix}} _ {p} ( mathbb {F} _ {q} [x] / (f (x)))}$ je ${ textstyle mathbb {F} _ {p}}$-prostor a jeho explicitní základ lze vypočítat v polynomiálním kruhu ${ textstyle mathbb {F} _ {p} [x, y] / (f, g)}$ výpočtem ${ textstyle (x ^ {i} y ^ {j}) ^ {p}}$ a stanovení lineárních rovnic na koeficientech ${ textový styl x, y}$ polynomy, které jsou splněny, pokud je opraven Frobeniem. Poznamenáváme, že v tomto okamžiku máme efektivně vypočítatelné kritérium neredukovatelnosti a zbývající analýza ukazuje, jak to použít k nalezení faktorů.

Algoritmus se nyní dělí na dva případy:

• V případě malých ${ textový styl}$ můžeme postavit libovolné ${ textstyle g in { text {Fix}} _ {p} ( mathbb {F} _ {q} [x] / (f (x))) setminus mathbb {F} _ {p}}$, a pak to u některých pozorujte ${ textstyle a in mathbb {F} _ {p}}$ existují ${ textový styl i, j}$ aby ${ textstyle g-a = 0 mod f_ {i}}$ a ${ textový styl g-a not = 0 mod f_ {j}}$. Takový ${ textstyle g-a}$ má netriviální faktor společný s ${ textstyle f (x)}$, které lze vypočítat pomocí gcd. Tak jako ${ textový styl}$ je malý, můžeme procházet všemi možnými způsoby ${ textstyle a}$.
• V případě velkých prvočísel, která jsou nutně zvláštní, lze využít skutečnosti, že náhodný nenulový prvek ${ textstyle mathbb {F} _ {p} ^ {*}}$ je čtverec s pravděpodobností ${ textový styl 1/2}$, a to mapa ${ textstyle x až x ^ { frac {p-1} {2}}}$ mapuje sadu nenulových čtverců na ${ textový styl 1}$a sada non-square na ${ textstyle -1}$. Pokud tedy vezmeme náhodný prvek ${ textstyle g in { text {Fix}} _ {p} ( mathbb {F} _ {q} [x] / f (x))}$, pak s velkou pravděpodobností ${ textstyle g ^ { frac {p-1} {2}} - 1}$ bude mít společný netriviální faktor ${ textstyle f (x)}$.

Další podrobnosti najdete na.^[1]

Aplikace

Jednou z důležitých aplikací Berlekampova algoritmu je výpočetní technika diskrétní logaritmy přes konečná pole ${ displaystyle mathbb {F} _ {p ^ {n}}}$, kde ${ displaystyle p}$ je hlavní a ${ displaystyle n geq 2}$. Výpočet diskrétních logaritmů je důležitým problémem kryptografie veřejného klíče a kódování kontroly chyb. Pro konečné pole je nejrychlejší známá metoda metoda indexového počtu, což zahrnuje faktorizaci prvků pole. Pokud reprezentujeme pole ${ displaystyle mathbb {F} _ {p ^ {n}}}$ obvyklým způsobem - tedy jako polynomy nad základním polem ${ displaystyle mathbb {F} _ {p}}$, snížený modulo, neredukovatelný polynom stupně ${ displaystyle n}$ - pak se jedná pouze o polynomiální faktorizaci, kterou poskytuje Berlekampův algoritmus.

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

Berlekampův algoritmus je přístupný v balíčku PARI / GP pomocí faktormod velení a WolframAlpha [1] webová stránka.

Viz také

• Polynomiální faktorizace
• Faktorizace polynomů přes konečné pole a testy neredukovatelnosti
• Algoritmus Cantor – Zassenhaus

Reference

• Berlekamp, ​​Elwyn R. (1967). "Faktorování polynomů přes konečná pole". Technický deník Bell System. 46: 1853–1859. doi:10.1002 / j.1538-7305.1967.tb03174.x. PAN  0219231. BSTJ Později publikováno v: Berlekamp, ​​Elwyn R. (1968). Algebraická teorie kódování. McGraw Hill. ISBN  0-89412-063-8.
• Knuth, Donald E. (1997). "4.6.2 Faktorizace polynomů". Seminumerické algoritmy. Umění počítačového programování. 2 (Třetí vydání.). Reading, Massachusetts: Addison-Wesley. 439–461, 678–691. ISBN  0-201-89684-2.