Algoritmus Berlekamp-Rabin

Algoritmus Berlekamp-Rabin (také Berlekampova metoda ) je pravděpodobnostní metoda pro nalezení kořenů polynomů na poli s polynomiální složitostí. Metoda byla popsána americkým matematikem Alvinem Berlekampem v roce 1970 [1] jako vedlejší produkt faktorizačního algoritmu pro polynomy nad konečnými tělesy a později (v roce 1979) byla upravena Michaelem Rabinem pro případ libovolných konečných těles [2]. . Původní verze algoritmu navržená Berlekampem v roce 1967 [3] nebyla polynomická [4] . Verze algoritmu publikovaná v roce 1970 na základě výsledků Zassenhaus pracovala s velkými hodnotami , ve které byla jako pomocník použita metoda title [1] . V době publikace byla metoda běžná v odborném prostředí, v literatuře se však nacházela jen zřídka [4] . $\mathbb {F} _{p}$ $p$

Historie

Metodu navrhl Alvin Berlekamp ve své práci na faktorizaci polynomů nad konečnými tělesy [1] . V tom je faktorizace polynomu na ireducibilní faktory nad polem redukována na nalezení kořenů některých dalších polynomů nad polem . Přitom v původní práci nebyl žádný důkaz o správnosti algoritmu [2] . Algoritmus dokončil a zobecnil na případ libovolných konečných polí Michael Rabin [2] . V roce 1986 popsal René Peralta podobný algoritmus [5] , který řeší problém hledání druhé odmocniny v poli [6] , a v roce 2000 byla Peraltova metoda zobecněna pro řešení kubických rovnic [7] . ${\mathbb F}_{{p^{k}}}$ $\mathbb {F} _{p}$ $\mathbb {F} _{p}$

V Berlekampově algoritmu je polynom nejprve reprezentován jako součin , kde je součin polynomů stupně . Potom faktorizace každého takového polynomu stupně je redukována na nalezení kořenů nového polynomu stupně . Článek představující faktorizační algoritmus také navrhl tři metody pro nalezení kořenů polynomu v Galoisově poli . První dva redukují hledání kořenů v poli na hledání kořenů v poli . Třetí metoda, která je předmětem tohoto článku, řeší problém hledání kořenů v poli , který spolu s dalšími dvěma řeší problém faktorizace [1] . ${\displaystyle f(x)=a_{0}+a_{1}x+\dots +a_{n}x^{n))$ $f(x)=h_{1}(x)h_{2}(x)\tečky h_{n}(x)$ $Ahoj}$ $r_{i}$ $i$ $Ahoj x)$ ${\displaystyle ir_{i))$ $H(x)$ $r_{i}$ ${\mathbb F}_{{p^{k}}}$ ${\mathbb F}_{{p^{k}}}$ $\mathbb {F} _{p}$ $\mathbb {F} _{p}$

Verze faktorizačního algoritmu navržená Berlekampem ve svém prvním článku v roce 1967 [3] běžela v roce , kde je počet ireducibilních faktorů polynomu. Algoritmus byl tedy nepolynomiální a byl nepraktický, když bylo prvočíslo dostatečně velké. V roce 1969 tento problém vyřešil Hans Zassenhaus , který ukázal, jak redukovat úzké hrdlo algoritmu na problém hledání kořenů nějakého polynomu [4] . V roce 1970 byl znovu publikován Berlekampův článek s přihlédnutím k řešením Zassenhause [1] . $O(n^{3}+prn)$ $r$ $p$

V roce 1980 provedl Michael Rabin rigorózní analýzu algoritmu, zobecnil jej pro práci s konečnými poli tvaru a dokázal, že pravděpodobnost chyby jedné iterace algoritmu nepřesahuje [2] a v roce 1981 Michael Ben- Nebo posílil tento odhad na , kde — počet různých kořenů polynomu [8] . Otázka existence polynomiálního deterministického algoritmu pro hledání kořenů polynomu nad konečným polem zůstává otevřená - hlavní algoritmy rozkladu polynomů, Berlekampův algoritmus a Cantor-Zassenhausův algoritmus jsou pravděpodobnostní. V roce 1981 Paul Camion ukázal [9] , že takový algoritmus existuje pro jakékoli dané číslo , ale tento výsledek je čistě teoretický a otázka možnosti sestrojení jím popisovaných množin v praxi zůstává otevřená [10] . ${\mathbb F}_{{p^{k}}}$ $1/2$ ${\textstyle 1-1/2^{k-1}+O\left(1/{\sqrt {p}}\right)}$ $k$ $f(x)$ $p$

V prvním vydání druhého svazku „ Umění programování “ o numerických algoritmech Donald Knuth píše, že podobné faktorizační postupy byly známy již v roce 1960, ale jen zřídka se nacházely ve veřejné doméně [4] . Jeden z prvních publikovaných příkladů použití metody lze nalézt v práci Golomba , Welshe a Halese z roku 1959 o faktorizaci trinomů nad , kde byl zvažován zvláštní případ [11] . $\mathbb {F} _{2}$ $p=2,z=1$

Algoritmus

Prohlášení o problému

Nechť je liché prvočíslo. Uvažujme polynom nad polem zbytků modulo . Je potřeba najít všechna čísla taková, aby pro všechny možné [2] [12] . $p$ ${\textstyle f(x)=a_{0}+a_{1}x+\tečky +a_{n}x^{n))$ $\mathbb {Z} _{p}$ $p$ ${\displaystyle \lambda _{1},\tečky ,\lambda _{k))$ ${\textstyle f(\lambda _{i})\equiv 0{\pmod {p))}$ $i$

Randomizace

Nechte _ Nalezení všech kořenů takového polynomu je ekvivalentní jeho rozdělení na lineární faktory. K nalezení takového rozdělení se stačí naučit, jak rozdělit polynom na libovolné dva faktory, a pak na ně rekurzivně spustit. K tomu zavedeme polynom , kde je náhodné číslo z . Pokud lze takový polynom reprezentovat jako součin , pak v podmínkách původního polynomu to znamená, že , což dává rozklad původního polynomu [1] [12] . ${\textstyle f(x)=(x-\lambda _{1})(x-\lambda _{2})\tečky (x-\lambda _{n})}$ ${\textstyle f_{z}(x)=f(xz)=(x-\lambda _{1}-z)(x-\lambda _{2}-z)\tečky (x-\lambda _{n }-z)}$ $z$ $\mathbb {Z} _{p}$ $f_{z}(x)=p_{0}(x)p_{1}(x)$ $f(x)=p_{0}(x+z)p_{1}(x+z)$ $f(x)$

Klasifikace prvků $\mathbb {F} _{p}$

Podle Eulerova kritéria je pro jakýkoli monomiál splněna právě jedna z následujících vlastností [1] : $(x-\lambda )$

Monomial je roven jestliže , $X$ $\lambda=0$
Monomial dělí jestliže je kvadratický zbytek modulo , ${\textstyle g_{0}(x)=(x^{(p-1)/2}-1)}$ $\lambda$ $p$
Monomial dělí if je kvadratický nezbytkový modulo this. ${\textstyle g_{1}(x)=(x^{(p-1)/2}+1)}$ $\lambda$

Pokud tedy není dělitelné , což lze zkontrolovat samostatně, pak se rovná součinu největších společných dělitelů a [12] . $f_{z}(x)$ $X$ $f_{z}(x)$ $\gcd(f_{z}(x);g_{0}(x))$ $\gcd(f_{z}(x);g_{1}(x))$

Berlekampova metoda

Výše uvedené vede k následujícímu algoritmu [1] :

Koeficienty polynomu jsou explicitně vypočteny , $f_{z}(x)=f(xz)$
Vypočítejte zbytek dělení postupným umocněním a odebráním zbytku , ${\textstyle x,x^{2},x^{2^{2)),x^{2^{3)),x^{2^{4)),\tečky ,x^{2^{ \lpodlaží \log _{2}p\rpodlaží }}}$ $f_{z}(x)$ $f_{z}(x)$
Binární umocnění vypočítá zbytek dělení pomocí polynomů vypočítaných v posledním kroku, ${\textstyle x^{(p-1)/2}}$ ${\textstyle f_{z}(x)}$
Jestliže , pak výše uvedené dává netriviální faktorizaci, ${\textstyle x^{(p-1)/2}\not \equiv \pm 1{\pmod {f_{z}(x)))}$ $\gcd$ $f_{z}(x)$
Jinak jsou všechny kořeny zároveň zbytky i nezbytky a vyplatí se vyzkoušet jinou hodnotu . $f_{z}(x)$ $z$

Pokud je také rozdělen nějakým polynomem , který nemá kořeny v , pak při výpočtu s a získáme rozdělení polynomu bez čtverců na netriviální faktory, takže algoritmus vám umožní najít všechny kořeny libovolného polynomy přes , a nejen ty, které jsou rozděleny do součinu monočlenů [12] . $f(x)$ $g(x)$ $\mathbb {Z} _{p}$ $\gcd$ $g_{0}(x)$ $g_{1}(x)$ $f_{z}(x)/g_{z}(x)$ $\mathbb {Z} _{p}$

Extrahování druhé odmocniny

Nechť je třeba řešit srovnání, jehož řešením jsou prvky a resp. Jejich nalezení je ekvivalentní rozkladu polynomu nad polem . V tomto konkrétním případě je úloha zjednodušena, protože pro řešení stačí vypočítat pouze . Pro výsledný polynom bude pravdivý právě jeden z výroků: ${\textstyle x^{2}\equiv a{\pmod {p}}}$ $\beta$ $-\beta$ ${\textstyle f(x)=x^{2}-a=(x-\beta )(x+\beta )}$ $\mathbb {Z} _{p}$ $\gcd(f_{z}(x);g_{0}(x))$

GCD je , což znamená, že a jsou zároveň kvadratickými nezbytky, $jeden$ $z+\beta$ $z-\beta$
GCD je , což znamená, že obě čísla jsou kvadratické zbytky, $f_{z}(x)$
GCD se rovná monomiálu , což znamená, že přesně jedno číslo ze dvou je kvadratický zbytek. $(xt)$

Ve třetím případě musí být výsledný monomiál roven nebo , nebo . To umožňuje zapsat řešení jako [1] . $(xz-\beta )$ $(x-z+\beta )$ ${\textstyle \beta =(tz){\pmod {p}}}$

Příklad

Pojďme vyřešit srovnání . Chcete-li to provést, musíte faktorizovat . Zvažme možné hodnoty : ${\textstyle x^{2}\equiv 5{\pmod {11}}}$ $f(x)=x^{2}-5=(x-\beta )(x+\beta )$ $z$

Nechte _ Odkud pak . Obě čísla jsou nezbytky a je třeba vzít další . $z=3$ $f_{z}(x)=(x-3)^{2}-5=x^{2}-6x+4$ $\gcd(x^{2}-6x+4;x^{5}-1)=1$ $3\pm \beta$ $z$

Nechte _ Odkud pak . Proto , proto . $z=2$ $f_{z}(x)=(x-2)^{2}-5=x^{2}-4x-1$ ${\textstyle \gcd(x^{2}-4x-1;x^{5}-1)\equiv x-9{\pmod {11))}$ ${\textstyle x-9=x-2-\beta }$ $\beta \equiv 7{\pmod {11}}$ ${\textstyle -\beta \equiv -7\equiv 4{\pmod {11}}}$

Ověření to ukazuje a je platné . ${\textstyle 7^{2}\equiv 49\equiv 5{\pmod {11))}$ ${\textstyle 4^{2}\equiv 16\equiv 5{\pmod {11))}$

Odůvodnění metody

Algoritmus najde rozdělení na netriviální faktory ve všech případech, kromě těch, ve kterých jsou všechna čísla současně zbytky nebo nezbytky. Podle teorie cyklotomie [1] , lze pravděpodobnost takové události pro případ, kdy samy jsou zároveň zbytky i nezbytky (tedy kdy se to pro náš postup nehodí), odhadnout jako [8] , kde je počet různých čísel mezi [1] . Pravděpodobnost chyby algoritmu tedy nepřesahuje . $f_{z}(x)$ ${\displaystyle z+\lambda _{1},z+\lambda _{2},\tečky ,z+\lambda _{n))$ ${\displaystyle \lambda _{1},\tečky ,\lambda _{n))$ $z=0$ $1/2^{k-1}$ $k$ ${\displaystyle \lambda _{1},\tečky ,\lambda _{n))$ $1/2$

Aplikace na faktorizaci polynomů

Z teorie konečných těles je známo , že je-li stupeň ireducibilního polynomu , pak takový polynom je dělitel a není dělitelem pro . $q(x)$ $d$ $x^{p^{d}}-x$ $x^{p^{t}}-x$ $t<d$

Postupně tedy zvažujeme polynomy kde a pro , můžeme rozdělit polynom na faktory tvaru , kde je součin všech ireducibilních polynomů stupně , které dělí polynom . Když známe stupeň , můžeme určit počet takových polynomů rovný . Nechte _ Pokud vezmeme v úvahu polynom , kde , pak pořadí takového polynomu v oboru musí dělit číslo . Pokud není dělitelný , pak je polynom dělitelný , ale ne . $h_{i}(x)=\gcd(f_{i}(x),x^{p^{i}}-1)$ $f_{1}(x)=f(x)$ $f_{i}(x)=f_{i-1}(x)/h_{i-1}(x)$ $i>1$ $f(x)$ $f(x)=h_{1}(x)\tečky h_{n}(x)$ $Ahoj x)$ $i$ $f(x)$ $Ahoj x)$ $r_{i}=\deg h_{i}(x)/i$ $h_{i}(x)=p_{1}(x)\tečky p_{r_{i}}(x)$ $p_{j}(xz)$ ${\textstyle z\in \mathbb {F} _{p}}$ $d_{j}$ ${\textstyle \mathbb {F} _{p^{i))}$ $p^{i}-1$ $d_{j}$ $d_{k}$ ${\textstyle x^{d_{j}}-x}$ ${\textstyle p_{j}(xz)}$ ${\textstyle p_{k}(xz)}$

Na základě toho Zassenhaus navrhl hledat dělitele polynomu ve tvaru , kde je nějaký dostatečně velký dělitel , například . V konkrétním případě se přesně získá Berlekampova metoda, jak je popsáno výše [4] . $h_{i}(xz)$ ${\textstyle \gcd(h_{i}(xz),x^{f}-1)}$ $F$ $p^{i}-1$ ${\textstyle f={\frac {p^{i}-1}{2}}}$ $i=1$

Otevírací doba

Krok za krokem lze dobu trvání jedné iterace algoritmu odhadnout následovně, za předpokladu, že stupeň polynomu je : $n$

Vzhledem k tomu, že podle Newtonova binomického vzorce je přechod z do proveden v , ${\textstyle (xz)^{k}=\sum \limits _{i=0}^{k}{\binom {k}{i}}(-z)^{ki}x^{i}}$ $f(x)$ $f(xz)$ $O(n^{2})$
Součin polynomů a odebrání zbytku jednoho polynomu modulo jiného se provádí v , takže výpočet se provádí v , ${\textstyle O(n^{2})}$ ${\textstyle x^{2^{k}}{\bmod {f}}_{z}(x)}$ ${\textstyle O(n^{2}\log p)}$
Podobně jako v předchozím bodě se binární umocňování provádí v , $O(n^{2}\log p)$
Přebírání ze dvou polynomů podle Euklidova algoritmu se provádí v . $\gcd$ $O(n^{2})$

Pro aritmetické operace s prvky lze tedy provést jednu iteraci algoritmu a nalezení všech kořenů polynomu vyžaduje průměr [8] . V konkrétním případě extrahování druhé odmocniny je hodnota dvě, takže doba běhu se odhaduje jako jedna iterace algoritmu [12] . $O(n^{2}\log p)$ $\mathbb {F} _{p}$ $O(n^{2}\log n\log p)$ $n$ $O(\log p)$

Poznámky

↑ 1 2 3 4 5 6 7 8 9 10 11 Berlekamp ER Rozdělení polynomů na velká konečná tělesa // Matematika počítání. - 1970. - Sv. 24 , iss. 111 . - str. 730-732 . — ISSN 0025-5718 . - doi : 10.1090/S0025-5718-1970-0276200-X .
↑ 1 2 3 4 5 Rabin M. Probabilistic Algorithms in Finite Fields // SIAM Journal on Computing. - 1980. - 1. května ( díl 9 , č . 2 ). - str. 273-280 . — ISSN 0097-5397 . - doi : 10.1137/0209024 . Archivováno z originálu 23. června 2019.
↑ 1 2 Berlekamp ER Faktorizace polynomů nad konečnými tělesy // The Bell System Technical Journal. - 1967. - říjen ( roč. 46 , 8. vydání ). - S. 1853-1859 . — ISSN 0005-8580 . - doi : 10.1002/j.1538-7305.1967.tb03174.x . Archivováno z originálu 17. února 2019.
↑ 1 2 3 4 5 Knuth DE Umění počítačového programování . - Reading, Massachusetts: Addison-Wesley Publishing Company, 1968. - Sv. 2. - S. 381-390. — 624 s. - ISBN 0-201-03802-1 . Archivováno 3. srpna 2019 na Wayback Machine
↑ Sze TW O odmocnění bez kvadratických nezbytků nad konečnými tělesy // Matematika počítání. - 2011. - 3. ledna ( díl 80 , výr. 275 ). - S. 1797-1811 . — ISSN 0025-5718 . - doi : 10.1090/s0025-5718-2011-02419-1 .
↑ Peralta R. Jednoduchý a rychlý pravděpodobnostní algoritmus pro výpočet druhých odmocnin modulo a prvočíslo (správně ) // IEEE Transactions on Information Theory. - 1986. - Listopad ( vol. 32 , es. 6 ). - S. 846-847 . — ISSN 0018-9448 . - doi : 10.1109/TIT.1986.1057236 . Archivováno z originálu 30. června 2019.
↑ Padró C., Sáez G. Odmocniny krychle v Zm // Applied Mathematics Letters. - 2002. - srpen ( vol. 15 , es. 6 ). - str. 703-708 . — ISSN 0893-9659 . - doi : 10.1016/s0893-9659(02)00031-9 .
↑ 1 2 3 Ben-Or M. Pravděpodobnostní algoritmy v konečných polích // 22. výroční sympozium o základech informatiky (sfcs 1981). - 1981. - Říjen. - str. 394-398 . - doi : 10.1109/SFCS.1981.37 . Archivováno z originálu 29. července 2019.
↑ Camion P. A Deterministic Algorithm for Factorizing Polynomials of Fq [X] // Kombinatorická matematika, sborník z Mezinárodního kolokvia o teorii grafů a kombinatorice. - Elsevier, 1983. - S. 149-157 . — ISBN 9780444865120 .
↑ Grenet B., van der Hoeven J., Lecerf G. Deterministické hledání kořenů nad konečnými poli pomocí Graeffeovy transformace // Použitelná algebra v inženýrství, komunikaci a počítačích. - 2015. - Sv. 27 , iss. 3 . — S. 239 . — ISSN 0938-1279 . - doi : 10.1007/s00200-015-0280-5 .
↑ Golomb SW, Hales A., Welch LR O rozkladu trinomů přes GF(2 ) // Sekvence posuvných registrů. - World Scientific, 2017. - Březen. - S. 90-108. - ISBN 978-981-4632-00-3 . - doi : 10.1142/9789814632010_0005 .
↑ 1 2 3 4 5 Menezes AJ, Blake IF, Gao XH, Mullin RC, Vanstone SA Aplikace konečných polí . - Springer USA, 1993. - S. 22-26. — 218p. - (The Springer International Series in Engineering and Computer Science). — ISBN 9780792392828 . Archivováno 30. června 2019 na Wayback Machine

Číselné teoretické algoritmy
Testy jednoduchosti	Mlynář Miller - Rabin Luca - Lemaire pepina Agravala - Kayala - Sasko Slavík - Strassen
Hledání prvočísel	Iterace přes dělitele Eratosthenovo síto Atkinovo síto Síto Sundarama
Faktorizace	Iterace přes dělitele Fermatova metoda p −1 Pollardova metoda Pollardův ρ-algoritmus Lehmannova metoda Metoda eliptické křivky (Lenstrův algoritmus) Dixonův algoritmus Čtvercové síto
Diskrétní logaritmus	Gelfond-Shanksův algoritmus Polig-Hellmanův algoritmus Pollardova ρ-metoda Pollardův algoritmus klokana Adlemanův algoritmus COS algoritmus
Hledání GCD	Euklidův algoritmus Pokročilý algoritmus Binární algoritmus
Modulová aritmetika	Montgomeryho algoritmus Čínská věta o zbytku
Násobení a dělení čísel	Algoritmus Karatsuba Toom-Cookův algoritmus Schönhage-Strassenův algoritmus Fuhrerův algoritmus Algoritmus Harvey-van der Hoeven Burnickel-Zieglerův algoritmus
Výpočet druhé odmocniny	Tonelli-Shanksův algoritmus Algoritmus Berlekamp-Rabin