Berlekamp-Rabin algoritmus

A Berlekamp-Rabin algoritmus (a Berlekamp-féle módszer is ) egy valószínűségi módszer a polinomok gyökereinek megtalálására polinomiális komplexitású mező felett . A módszert Alvin Berlekamp amerikai matematikus írta le 1970-ben [1] , mint a véges mezők feletti polinomok faktorizációs algoritmusának melléktermékét, majd később (1979-ben) Michael Rabin módosította tetszőleges véges mezők esetére [2]. . A Berlekamp által 1967-ben [3] javasolt algoritmus eredeti változata nem volt polinom [4] . Az algoritmus 1970-ben Zassenhaus eredményein alapuló változata nagy értékekkel dolgozott, amelyben a cím módszert használták segédként [1] . A módszer megjelenése idején a szakmai környezetben elterjedt, a szakirodalomban azonban ritkán található [4] . $\mathbb {F} _{p}$ $p$

Történelem

A módszert Alvin Berlekamp javasolta a polinomok véges mezők feletti faktorizálásáról szóló munkájában [1] . Ebben a polinom egy mező feletti irreducibilis faktorokká alakítása arra redukálódik, hogy megkeressük néhány más polinom gyökerét egy mező felett . Ugyanakkor az eredeti munkában nem volt bizonyíték az algoritmus helyességére [2] . Az algoritmust Michael Rabin véglegesítette és általánosította tetszőleges véges mezők esetére [2] . 1986-ban René Peralta leírt egy hasonló algoritmust [5] , amely megoldja a négyzetgyök keresésének problémáját egy mezőben [6] , 2000-ben pedig Peralta módszerét általánosították a köbegyenletek megoldására [7] . ${\mathbb F}_{{p^{k))}$ $\mathbb {F} _{p}$ $\mathbb {F} _{p}$

A Berlekamp -algoritmusban egy polinomot először szorzatként ábrázolunk , ahol a fokszámú polinomok szorzata . Ezután minden ilyen fokú polinom faktorizálását az új fokú polinom gyökeinek megtalálására redukáljuk . A faktorizációs algoritmust bemutató cikk három módszert is javasolt a polinom gyökereinek megtalálására Galois mezőben . Az első kettő levezeti a gyökerek keresését egy mezőben a gyökerek megtalálására egy mezőben . A cikk tárgyát képező harmadik módszer megoldja a mezőben való gyökerek megtalálásának problémáját , amely a másik kettővel együtt megoldja a faktorizációs problémát [1] . ${\displaystyle f(x)=a_{0}+a_{1}x+\dots +a_{n}x^{n))$ $f(x)=h_{1}(x)h_{2}(x)\dots h_{n}(x)$ $Szia}$ $r_{i}$ $én$ $Szia)$ ${\displaystyle ir_{i))$ $H(x)$ $r_{i}$ ${\mathbb F}_{{p^{k))}$ ${\mathbb F}_{{p^{k))}$ $\mathbb {F} _{p}$ $\mathbb {F} _{p}$

A faktorizációs algoritmus Berlekamp által 1967-ben megjelent első írásában [3] javasolt változata futott be , ahol a polinom irreducibilis tényezőinek száma. Így az algoritmus nem polinomiális, és nem volt praktikus, ha a prímszám elég nagy volt. 1969-ben ezt a problémát Hans Zassenhaus oldotta meg , és megmutatta, hogyan csökkenthető az algoritmus szűk keresztmetszete valamilyen polinom gyökereinek megtalálásának problémájára [4] . 1970-ben Berlekamp cikkét Zassenhaus megoldásait figyelembe véve [1] újra kiadták . $O(n^{3}+prn)$ $r$ $p$

1980-ban Michael Rabin elvégezte az algoritmus szigorú elemzését, általánosította úgy, hogy véges alakú mezőkkel dolgozzon , és bebizonyította, hogy az algoritmus egy iterációjának hibavalószínűsége nem haladja meg a [2] -t, majd 1981-ben Michael Ben- Vagy megerősítette ezt a becslést -ra , ahol - a polinom különböző gyökeinek száma [8] . A polinomiális determinisztikus algoritmus létezésének kérdése egy véges mező feletti polinom gyökereinek megtalálására nyitva marad - a fő polinomfaktorizációs algoritmusok, a Berlekamp-algoritmus és a Cantor-Zassenhaus algoritmus valószínűségi. 1981-ben Paul Camion kimutatta [9] , hogy létezik ilyen algoritmus bármely adott számra , de ez az eredmény pusztán elméleti, és az általa leírt halmazok gyakorlati megalkotásának lehetősége nyitva marad [10] . ${\mathbb F}_{{p^{k))}$ $1/2$ ${\textstyle 1-1/2^{k-1}+O\left(1/{\sqrt {p}}\right)}$ $k$ $f(x)$ $p$

A numerikus algoritmusokról szóló "A programozás művészete " második kötetének első kiadásában Donald Knuth azt írja, hogy hasonló faktorizációs eljárások 1960-ban ismertek voltak, de ritkán voltak nyilvánosak [4] . A módszer használatára az egyik első publikált példát Golomb , Welsh és Hales 1959-ből származó, a trinomiálisok faktorizálásáról szóló munkájában találjuk , ahol egy speciális esetet vettek figyelembe [11] . $\mathbb {F} _{2}$ $p=2,z=1$

Algoritmus

A probléma leírása

Legyen páratlan prímszám. Tekintsünk egy polinomot a maradékok mezője felett modulo . Meg kell találni az összes számot úgy, hogy minden lehetséges [2] [12] esetén . $p$ ${\textstyle f(x)=a_{0}+a_{1}x+\pontok +a_{n}x^{n))$ $\mathbb {Z} _{p}$ $p$ ${\displaystyle \lambda _{1},\dots ,\lambda _{k))$ ${\textstyle f(\lambda _{i})\equiv 0{\pmod {p))}$ $én$

Randomizálás

Hadd . Egy ilyen polinom összes gyökerének megtalálása egyenértékű a lineáris tényezőkre való felosztással. Egy ilyen partíció megtalálásához elég megtanulni, hogyan lehet a polinomot két faktorra felosztani, majd rekurzívan belefutni. Ehhez bevezetünk egy polinomot , ahol a -ból származó véletlen szám . Ha egy ilyen polinom szorzatként reprezentálható , akkor az eredeti polinom szempontjából ez azt jelenti, hogy , ami az eredeti polinom faktorizációját adja [1] [12] . ${\textstyle f(x)=(x-\lambda _{1})(x-\lambda _{2})\dots (x-\lambda _{n})}$ ${\textstyle f_{z}(x)=f(xz)=(x-\lambda _{1}-z)(x-\lambda _{2}-z)\dots (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)$

Az elemek osztályozása $\mathbb {F} _{p}$

Az Euler-kritérium szerint bármely monom esetében pontosan az alábbi tulajdonságok egyike teljesül [1] : $(x-\lambda )$

A monom egyenlő azzal , ha $x$ $\lambda=0$
A monom osztja , ha egy négyzetes maradék modulo , ${\textstyle g_{0}(x)=(x^{(p-1)/2}-1)}$ $\lambda$ $p$
A monomiális osztja az if másodfokú nem-maradék modulo ezt. ${\textstyle g_{1}(x)=(x^{(p-1)/2}+1)}$ $\lambda$

Így ha nem osztható -vel , ami külön is ellenőrizhető, akkor egyenlő a legnagyobb közös osztók és [12] szorzatával . $f_{z}(x)$ $x$ $f_{z}(x)$ $\gcd(f_{z}(x);g_{0}(x))$ $\gcd(f_{z}(x);g_{1}(x))$

Berlekamp módszer

A fentiek a következő algoritmushoz vezetnek [1] :

A polinom együtthatói explicit módon vannak kiszámítva , $f_{z}(x)=f(xz)$
Számítsa ki az osztás maradékát egymás utáni négyzetesítéssel, és vegye fel a maradékot , ${\textstyle x,x^{2},x^{2^{2)),x^{2^{3)),x^{2^{4)),\dots ,x^{2^{ \lfloor \log _{2}p\rfloor }}}$ $f_{z}(x)$ $f_{z}(x)$
A bináris hatványozás az osztás maradékát az utolsó lépésben kiszámított polinomok felhasználásával számítja ki, ${\textstyle x^{(p-1)/2}}$ ${\textstyle f_{z}(x)}$
Ha , akkor a fentiek nem triviális faktorizációt adnak, ${\textstyle x^{(p-1)/2}\not \equiv \pm 1{\pmod {f_{z}(x)))}$ $\gcd$ $f_{z}(x)$
Ellenkező esetben az összes gyökér egyszerre maradvány vagy nem maradvány, és érdemes más értékkel próbálkozni . $f_{z}(x)$ $z$

Ha olyan polinomtal is elosztjuk, amelynek nincs gyöke -ben , akkor a és -vel történő számításkor a négyzet nélküli polinom nem triviális tényezőkre való felosztását kapjuk, így az algoritmus lehetővé teszi, hogy megtalálja bármelyik gyökét. feletti polinomok , és nem csak azok, amelyek monomok szorzatára vannak felbontva [12] . $f(x)$ $g(x)$ $\mathbb {Z} _{p}$ $\gcd$ $g_{0}(x)$ $g_{1}(x)$ $f_{z}(x)/g_{z}(x)$ $\mathbb {Z} _{p}$

A négyzetgyök kinyerése

Legyen szükséges olyan összehasonlítást megoldani, amelynek megoldásai az elemek , ill. Megtalálásuk egyenértékű egy polinom mező feletti faktorizálásával . Ebben a konkrét esetben a feladat leegyszerűsödik, mivel a megoldáshoz elég csak számolni . A kapott polinomra pontosan az egyik állítás lesz igaz: ${\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))$

A GCD , ami azt jelenti, hogy és egyben négyzetes nem maradékok, $egy$ $z+\beta$ $z-\beta$
A GCD , ami azt jelenti, hogy mindkét szám másodfokú maradék, $f_{z}(x)$
A GCD egyenlő egy monomimmal , ami azt jelenti, hogy kettőből pontosan egy szám másodfokú maradék. ${\megjelenítési stílus (xt)}$

A harmadik esetben a kapott monomnak egyenlőnek kell lennie vagy , vagy . Ez lehetővé teszi, hogy a megoldást [1] -ként írjuk le . $(xz-\beta )$ $(x-z+\beta )$ ${\textstyle \beta =(tz){\pmod {p}}}$

Példa

Oldjuk meg az összehasonlítást . Ehhez faktorizálásra van szükség . Nézzük a lehetséges értékeket : ${\textstyle x^{2}\equiv 5{\pmod {11}}}$ $f(x)=x^{2}-5=(x-\beta )(x+\beta )$ $z$

Hadd . Aztán honnan . Mindkét szám nem maradék, ezért másikat kell venni . $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$

Hadd . Aztán honnan . Ezért , tehát . $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}}}$

Az ellenőrzés ezt mutatja és érvényes . ${\textstyle 7^{2}\equiv 49\equiv 5{\pmod {11))}$ ${\textstyle 4^{2}\equiv 16\equiv 5{\pmod {11))}$

A módszer indoklása

Az algoritmus minden esetben megtalálja a nem triviális faktorokra való felosztást , kivéve azokat, amelyekben minden szám egyidejűleg maradék vagy nem maradék. A ciklotómia elmélete [1] szerint egy ilyen esemény valószínűsége arra az esetre, ha maguk is egyidejűleg maradékok vagy nem-maradékok (vagyis amikor az eljárásunkhoz nem alkalmas) a következőképpen becsülhető meg. [8] , ahol a különböző számok száma az [1] között . Így az algoritmus hibájának valószínűsége nem haladja meg a -t . $f_{z}(x)$ ${\displaystyle z+\lambda _{1},z+\lambda _{2},\dots ,z+\lambda _{n))$ ${\displaystyle \lambda _{1},\dots ,\lambda _{n))$ $z=0$ $1/2^{k-1}$ $k$ ${\displaystyle \lambda _{1},\dots ,\lambda _{n))$ $1/2$

Alkalmazás polinomok faktorizálására

A véges mezők elméletéből ismert, hogy ha egy irreducibilis polinom foka , akkor az ilyen polinom osztó , és nem osztója -nak . $q(x)$ $d$ $x^{p^{d}}-x$ $x^{p^{t}}-x$ $t<d$

Így szekvenciálisan figyelembe véve azokat a polinomokat , ahol és -re , feloszthatjuk a polinomot alakú faktorokra , ahol az összes , a polinomot osztó fokszámú irreducibilis polinom szorzata . Fokának ismeretében meg tudjuk határozni az ilyen polinomok számát . Hadd . Ha figyelembe vesszük azt a polinomot , ahol , akkor egy ilyen polinom sorrendjének a mezőben osztania kell a számot . Ha nem osztható -vel , akkor a polinom osztható -vel, de -vel nem . $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)\dots h_{n}(x)$ $Szia)$ $én$ $f(x)$ $Szia)$ $r_{i}=\deg h_{i}(x)/i$ $h_{i}(x)=p_{1}(x)\pontok 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)}$

Ennek alapján Zassenhaus azt javasolta, hogy keressünk egy polinom osztóit az alakban , ahol van valami kellően nagy osztó , például . Egy adott esetben pontosan a Berlekamp-módszert kapjuk a fent leírtak szerint [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$

Nyitva tartás

Lépésről lépésre az algoritmus egy iterációjának futási ideje a következőképpen becsülhető meg, feltételezve, hogy a polinom foka : $n$

Figyelembe véve, hogy a Newton-féle binomiális képlet szerint az átmenet -ról -ra -ben történik , ${\textstyle (xz)^{k}=\sum \limits _{i=0}^{k}{\binom {k}{i}}(-z)^{ki}x^{i}}$ $f(x)$ $f(xz)$ $O(n^{2})$
A polinomok szorzata és egy másik polinom modulo maradékának vétele -ben történik , így a számítás -ben történik , ${\textstyle O(n^{2})}$ ${\textstyle x^{2^{k}}{\bmod {f}}_{z}(x)}$ ${\textstyle O(n^{2}\log p)}$
Az előző ponthoz hasonlóan a bináris hatványozást a következőben hajtjuk végre , $O(n^{2}\log p)$
Az Euklidész algoritmus szerinti két polinomból való vétel a -ban történik . $\gcd$ $O(n^{2})$

Így az algoritmus egy iterációja végrehajtható elemekkel végzett aritmetikai műveleteknél , és a polinom összes gyökének megtalálásához átlagot kell [8] . A négyzetgyök kinyerésének adott esetben az érték kettő, így a futási időt az algoritmus egy iterációjaként becsüljük [12] . $O(n^{2}\log p)$ $\mathbb {F} _{p}$ $O(n^{2}\log n\log p)$ $n$ $O(\log p)$

Jegyzetek

↑ 1 2 3 4 5 6 7 8 9 10 11 Berlekamp ER Polinomok faktorálása nagy véges mezőkön // Számítási matematika. - 1970. - 1. évf. 24 , iss. 111 . - P. 730-732 . — ISSN 0025-5718 . - doi : 10.1090/S0025-5718-1970-0276200-X .
↑ 1 2 3 4 5 Rabin M. Valószínűségi algoritmusok véges mezőkben // SIAM Journal on Computing. - 1980. - május 1. ( 9. kötet , 2. szám ). - 273-280 . — ISSN 0097-5397 . - doi : 10.1137/0209024 . Archiválva az eredetiből 2019. június 23-án.
↑ 1 2 Berlekamp ER Polinomok faktorálása véges mezőkön // The Bell System Technical Journal. - 1967. - október ( 46. évf. , 8. szám ). - P. 1853-1859 . — ISSN 0005-8580 . - doi : 10.1002/j.1538-7305.1967.tb03174.x . Archiválva az eredetiből 2019. február 17-én.
↑ 1 2 3 4 5 Knuth DE A számítógépes programozás művészete . - Reading, Massachusetts: Addison-Wesley Publishing Company, 1968. - Vol. 2. - P. 381-390. — 624 p. - ISBN 0-201-03802-1 . Archiválva : 2019. augusztus 3. a Wayback Machine -nél
↑ Sze TW Négyzetgyökök felvételéről másodfokú nemmaradékok nélkül véges mezők felett // Mathematics of Computation. - 2011. - január 3. ( 80. évf. , 275. szám ). - P. 1797-1811 . — ISSN 0025-5718 . - doi : 10.1090/s0025-5718-2011-02419-1 .
↑ Peralta R. Egy egyszerű és gyors valószínűségi algoritmus négyzetgyökök számításához prímszám modulo (Korresp. ) // IEEE Transactions on Information Theory. - 1986. - november ( 32. évf. , 6. szám ). - P. 846-847 . — ISSN 0018-9448 . - doi : 10.1109/TIT.1986.1057236 . Az eredetiből archiválva : 2019. június 30.
↑ Padró C., Sáez G. Kockagyökerezés a Zm-ben // Applied Mathematics Letters. - 2002. - augusztus ( 15. évf. , 6. szám ). - P. 703-708 . — ISSN 0893-9659 . - doi : 10.1016/s0893-9659(02)00031-9 .
↑ 1 2 3 Ben-Or M. Valószínűségi algoritmusok véges mezőkben // 22nd Annual Symposium on Foundations of Computer Science (sfcs, 1981). - 1981. - október. - P. 394-398 . - doi : 10.1109/SFCS.1981.37 . Archiválva az eredetiből 2019. július 29-én.
↑ Camion P. Determinisztikus algoritmus az Fq [X] polinomjainak faktorizálására // Kombinatorikus matematika, Proceedings of the International Colloquium on Graph Theory and Combinatorics. - Elsevier, 1983. - P. 149-157 . — ISBN 9780444865120 .
↑ Grenet B., van der Hoeven J., Lecerf G. Determinisztikus gyökkeresés véges mezők felett Graeffe-transzformációk segítségével // Alkalmazható algebra a mérnöki, kommunikációs és számítástechnikai területen. - 2015. - Kt. 27 , iss. 3 . - 239. o . — ISSN 0938-1279 . - doi : 10.1007/s00200-015-0280-5 .
↑ Golomb SW, Hales A., Welch LR A trinomiálisok faktorizációjáról GF(2 ) felett // Shift Register Sequences. - World Scientific, 2017. - márc. - P. 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 Applications of Finite Fields . - Springer USA, 1993. - P. 22-26. — 218p. - (The Springer International Series in Engineering and Computer Science). — ISBN 9780792392828 . Archiválva : 2019. június 30. a Wayback Machine -nél

Számelméleti algoritmusok
Egyszerűség tesztek	Molnár Miller – Rabin Luca - Lemaire pepina Agrawala – Kayala – Szászország Nightingale - Strassen
Prímszámok keresése	Iteráció osztók felett Eratoszthenész szita Atkin szitája Szita Sundarama
Faktorizáció	Iteráció osztók felett Fermat módszer p −1 Pollard-módszer Pollard ρ-algoritmusa Lehmann módszer Elliptikus görbe módszer (Lenstra-algoritmus) Dixon algoritmusa Négyzet alakú szita
Diszkrét logaritmus	Gelfond-Shanks algoritmus Polig-Hellman algoritmus Pollard ρ-módszere Pollard kenguru algoritmusa Adleman algoritmusa COS algoritmus
GCD keresése	Euklidész algoritmusa Speciális algoritmus Bináris algoritmus
Modulo aritmetika	Montgomery algoritmusa Kínai maradék tétel
Számok szorzása és osztása	Karatsuba algoritmus Toom-Cook algoritmus Schönhage-Strassen algoritmus Führer algoritmus Harvey-van der Hoeven algoritmus Burnickel-Ziegler algoritmus
A négyzetgyök kiszámítása	Tonelli-Shanks algoritmus Berlekamp-Rabin algoritmus