Algoritmul Berlekamp-Rabin

Algoritmul Berlekamp-Rabin (de asemenea metoda lui Berlekamp ) este o metodă probabilistică pentru găsirea rădăcinilor polinoamelor într- un câmp cu complexitate polinomială . Metoda a fost descrisă de matematicianul american Alvin Berlekamp în 1970 [1] ca o derivație a algoritmului de factorizare pentru polinoame peste câmpuri finite și a fost ulterior (în 1979) modificată de Michael Rabin pentru cazul câmpurilor finite arbitrare [2] . Versiunea originală a algoritmului propus de Berlekamp în 1967 [3] nu era polinomială [4] . Versiunea algoritmului publicată în 1970 pe baza rezultatelor lui Zassenhaus a lucrat cu valori mari ale , în care metoda titlului a fost folosită ca ajutor [1] . La momentul publicării, metoda era comună în mediul profesional, dar rar întâlnită în literatură [4] . $\mathbb {F} _{p}$ $p$

Istorie

Metoda a fost propusă de Alvin Berlekamp în lucrarea sa despre factorizarea polinoamelor pe câmpuri finite [1] . În ea, factorizarea unui polinom în factori ireductibili dintr-un câmp se reduce la găsirea rădăcinilor altor polinoame peste un câmp . În același timp, în lucrarea originală nu a existat nicio dovadă a corectitudinii algoritmului [2] . Algoritmul a fost finalizat și generalizat în cazul câmpurilor finite arbitrare de Michael Rabin [2] . În 1986, René Peralta a descris un algoritm similar [5] care rezolvă problema găsirii rădăcinii pătrate într-un câmp [6] , iar în 2000 metoda lui Peralta a fost generalizată pentru a rezolva ecuațiile cubice [7] . ${\mathbb F}_{{p^{k))}$ $\mathbb {F} _{p}$ $\mathbb {F} _{p}$

În algoritmul lui Berlekamp , un polinom este mai întâi reprezentat ca un produs , unde este produsul polinoamelor de grad . Apoi factorizarea fiecărui astfel de polinom de grad se reduce la găsirea rădăcinilor noului polinom de grad . Articolul de introducere a algoritmului de factorizare a propus trei metode de găsire a rădăcinilor unui polinom într- un câmp Galois . Primele două reduc găsirea rădăcinilor într-un câmp la găsirea rădăcinilor într-un câmp . A treia metodă, care face obiectul acestui articol, rezolvă problema găsirii rădăcinilor în câmpul , care, împreună cu celelalte două, rezolvă problema factorizării [1] . $f(x)=a_{0}+a_{1}x+\dots +a_{n}x^{n)$ $f(x)=h_{1}(x)h_{2}(x)\dots h_{n}(x)$ $Bună}$ $r_{i}$ $i$ $Salut x)$ $ir_{i)$ $H(x)$ $r_{i}$ ${\mathbb F}_{{p^{k))}$ ${\mathbb F}_{{p^{k))}$ $\mathbb {F} _{p}$ $\mathbb {F} _{p}$

Versiunea algoritmului de factorizare propusă de Berlekamp în prima sa lucrare din 1967 [3] a rulat în , unde este numărul de factori ireductibili ai polinomului. Astfel, algoritmul a fost non-polinom și a fost nepractic atunci când numărul prim era suficient de mare. În 1969, această problemă a fost rezolvată de Hans Zassenhaus , care a arătat cum se reduce blocajul algoritmului la problema găsirii rădăcinilor unui polinom [4] . În 1970, articolul lui Berlekamp a fost republicat, ținând cont de soluțiile lui Zassenhaus [1] . $O(n^{3}+prn)$ $r$ $p$

În 1980, Michael Rabin a efectuat o analiză riguroasă a algoritmului, l-a generalizat pentru a lucra cu câmpuri finite de forma , și a demonstrat că probabilitatea de eroare a unei iterații a algoritmului nu depășește [2] , iar în 1981 Michael Ben- Sau a consolidat această estimare la , unde — numărul de rădăcini diferite ale polinomului [8] . Întrebarea existenței unui algoritm determinist polinom pentru găsirea rădăcinilor unui polinom peste un câmp finit rămâne deschisă - principalii algoritmi de factorizare polinomială , algoritmul Berlekamp și algoritmul Cantor-Zassenhaus sunt probabilistice. În 1981, Paul Camion a arătat [9] că un astfel de algoritm există pentru orice număr dat , dar acest rezultat este pur teoretic și întrebarea posibilității de a construi mulțimile descrise de el în practică rămâne deschisă [10] . ${\mathbb F}_{{p^{k))}$ $1/2$ ${\textstyle 1-1/2^{k-1}+O\left(1/{\sqrt {p}}\right)}$ $k$ $f(x)$ $p$

În prima ediție a celui de-al doilea volum din „The Art of Programming ” despre algoritmi numerici, Donald Knuth scrie că proceduri similare de factorizare erau cunoscute până în 1960, dar au fost rareori găsite în domeniul public [4] . Unul dintre primele exemple publicate de utilizare a metodei poate fi găsit în lucrarea lui Golomb , Welsh și Hales din 1959 privind factorizarea trinoamelor peste , unde a fost luat în considerare un caz special [11] . $\mathbb {F} _{2}$ $p=2,z=1$

Algoritm

Enunțul problemei

Fie un număr prim impar. Se consideră un polinom peste câmpul resturilor modulo . Este necesar să găsiți toate numerele astfel încât pentru toate posibilele [2] [12] . $p$ ${\textstyle f(x)=a_{0}+a_{1}x+\dots +a_{n}x^{n)}$ $\mathbb {Z} _{p}$ $p$ $\lambda _{1},\dots,\lambda _{k)$ ${\textstyle f(\lambda _{i})\equiv 0{\pmod {p))}$ $i$

Randomizare

Lasă . Găsirea tuturor rădăcinilor unui astfel de polinom este echivalentă cu împărțirea lui în factori liniari. Pentru a găsi o astfel de partiție, este suficient să învățați cum să împărțiți polinomul în oricare doi factori și apoi să rulați recursiv în ei. Pentru a face acest lucru, introducem un polinom , unde este un număr aleator din . Dacă un astfel de polinom poate fi reprezentat ca un produs , atunci în ceea ce privește polinomul original aceasta înseamnă că , ceea ce dă o factorizare a polinomului original [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)$

Clasificarea elementelor $\mathbb {F} _{p}$

Conform criteriului Euler, pentru orice monom este îndeplinită exact una dintre următoarele proprietăți [1] : $(x-\lambda )$

Monomiul este egal cu dacă , $X$ $\lambda=0$
Monomiul se împarte dacă este un rest patratic modulo , ${\textstyle g_{0}(x)=(x^{(p-1)/2}-1)}$ $\lambda$ $p$
Monomiul se împarte dacă este un non-reziduu pătratic modulo this. ${\textstyle g_{1}(x)=(x^{(p-1)/2}+1)}$ $\lambda$

Astfel, dacă nu este divizibil cu , ceea ce poate fi verificat separat, atunci este egal cu produsul celor mai mari divizori comuni și [12] . $f_{z}(x)$ $X$ $f_{z}(x)$ $\gcd(f_{z}(x);g_{0}(x))$ $\gcd(f_{z}(x);g_{1}(x))$

Metoda Berlekamp

Cele de mai sus conduce la următorul algoritm [1] :

Coeficienții polinomului sunt calculați în mod explicit , $f_{z}(x)=f(xz)$
Calculați restul împărțirii prin pătrat succesiv și luând restul de , ${\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)$
Exponentiația binară calculează restul diviziunii folosind polinoamele calculate în ultimul pas, ${\textstyle x^{(p-1)/2}}$ ${\textstyle f_{z}(x)}$
Dacă , atunci cele de mai sus oferă o factorizare non-trivială , ${\textstyle x^{(p-1)/2}\nu \equiv \pm 1{\pmod {f_{z}(x)))}$ $\gcd$ $f_{z}(x)$
În caz contrar, toate rădăcinile sunt reziduuri sau nereziduuri în același timp și merită să încercați o altă valoare . $f_{z}(x)$ $z$

Dacă este, de asemenea, împărțit la un polinom care nu are rădăcini în , atunci când se calculează cu și , se va obține o partiție a polinomului fără pătrat în factori netriviali, astfel încât algoritmul vă permite să găsiți toate rădăcinile oricărui polinoame peste , și nu doar cele care sunt rupte într-un produs de monomii [12] . $f(x)$ $g(x)$ $\mathbb {Z} _{p}$ $\gcd$ $g_{0}(x)$ $g_{1}(x)$ $f_{z}(x)/g_{z}(x)$ $\mathbb {Z} _{p}$

Extragerea rădăcinii pătrate

Să fie necesar să se rezolve o comparație ale cărei soluții sunt elementele și respectiv. Găsirea lor este echivalentă cu factorizarea unui polinom peste un câmp . În acest caz particular, problema este simplificată, deoarece pentru soluție este suficient să calculați numai . Pentru polinomul rezultat, exact una dintre afirmații va fi adevărată: ${\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 este , ceea ce implică faptul că și sunt nereziduuri pătratice în același timp, $unu$ $z+\beta$ $z-\beta$
GCD este , ceea ce implică că ambele numere sunt reziduuri pătratice, $f_{z}(x)$
GCD este egal cu un monom , ceea ce implică faptul că exact un număr din doi este un reziduu pătratic. $(xt)$

În al treilea caz, monomul rezultat trebuie să fie egal cu sau , sau . Acest lucru permite ca soluția să fie scrisă ca [1] . $(xz-\beta)$ $(x-z+\beta)$ ${\textstyle \beta =(tz){\pmod {p}}}$

Exemplu

Să rezolvăm comparația . Pentru a face acest lucru, trebuie să factorizați . Să luăm în considerare valorile posibile : ${\textstyle x^{2}\equiv 5{\pmod {11}}}$ $f(x)=x^{2}-5=(x-\beta )(x+\beta )$ $z$

Lasă . Apoi de unde . Ambele numere sunt nereziduuri și trebuie să luați un altul . $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$

Lasă . Apoi de unde . De aici , de aici . $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}}}$

Verificarea arată că și este validă . ${\textstyle 7^{2}\equiv 49\equiv 5{\pmod {11))}$ ${\textstyle 4^{2}\equiv 16\equiv 5{\pmod {11))}$

Justificarea metodei

Algoritmul găsește o partiție în factori non-triviali în toate cazurile, cu excepția celor în care toate numerele sunt reziduuri sau nereziduuri în același timp. Conform teoriei ciclotomiei [1] , probabilitatea unui astfel de eveniment pentru cazul în care ei înșiși sunt ambele reziduuri sau nereziduuri în același timp (adică atunci când nu este potrivit pentru procedura noastră) poate fi estimată ca [8] , unde este numărul de numere diferite dintre [1] . Astfel, probabilitatea de eroare a algoritmului nu depășește . $f_{z}(x)$ $z+\lambda _{1},z+\lambda _{2},\dots,z+\lambda _{n)$ $\lambda _{1},\dots,\lambda _{n)$ $z=0$ $1/2^{k-1}$ $k$ $\lambda _{1},\dots,\lambda _{n)$ $1/2$

Aplicație la factorizarea polinoamelor

Din teoria câmpurilor finite se știe că, dacă gradul unui polinom ireductibil este , atunci un astfel de polinom este un divizor și nu este un divizor pentru . $q(x)$ $d$ $x^{p^{d}}-x$ $x^{p^{t}}-x$ $t<d$

Astfel, luând în considerare secvențial polinoamele unde și pentru , putem împărți polinomul în factori de forma , unde este produsul tuturor polinoamelor ireductibile de grad care împart polinomul . Cunoscând gradul de , putem determina numărul de astfel de polinoame egal cu . Lasă . Dacă luăm în considerare polinomul , unde , atunci ordinea unui astfel de polinom în câmp trebuie să împartă numărul . Dacă nu este divizibil cu , atunci polinomul este divizibil cu , dar nu cu . $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)$ $Salut x)$ $i$ $f(x)$ $Salut x)$ $r_{i}=\deg h_{i}(x)/i$ $h_{i}(x)=p_{1}(x)\dots 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)}$

Pe baza acestui fapt, Zassenhaus a sugerat să se caute divizori ai unui polinom sub forma , unde este un divizor suficient de mare , de exemplu, . Într-un caz particular , exact metoda Berlekamp este obținută așa cum este descris mai sus [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$

Orele de deschidere

Pas cu pas, timpul de rulare a unei iterații a algoritmului poate fi estimat după cum urmează, presupunând că gradul polinomului este : $n$

Având în vedere că conform formulei binomiale a lui Newton , trecerea de la la se face în , ${\textstyle (xz)^{k}=\sum \limits _{i=0}^{k}{\binom {k}{i}}(-z)^{ki}x^{i}}$ $f(x)$ $f(xz)$ $O(n^{2})$
Produsul polinoamelor și luând restul unui polinom modulo altul se face în , deci calculul se face în , ${\textstyle O(n^{2})}$ ${\textstyle x^{2^{k}}{\bmod {f}}_{z}(x)}$ ${\textstyle O(n^{2}\log p)}$
Similar cu punctul anterior, exponentiația binară se face în , $O(n^{2}\log p)$
Preluarea din două polinoame conform algoritmului Euclid se face în . $\gcd$ $O(n^{2})$

Astfel, o iterație a algoritmului poate fi efectuată pentru operații aritmetice cu elemente , iar găsirea tuturor rădăcinilor polinomului necesită o medie [8] . În cazul particular al extragerii rădăcinii pătrate, valoarea este două, deci timpul de rulare este estimat ca o iterație a algoritmului [12] . $O(n^{2}\log p)$ $\mathbb {F} _{p}$ $O(n^{2}\log n\log p)$ $n$ $O(\log p)$

Note

↑ 1 2 3 4 5 6 7 8 9 10 11 Berlekamp ER Factorizarea polinoamelor pe câmpuri finite mari // Matematica calculului. - 1970. - Vol. 24 , iss. 111 . - P. 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 mai ( vol. 9 , iss. 2 ). - P. 273-280 . — ISSN 0097-5397 . - doi : 10.1137/0209024 . Arhivat din original pe 23 iunie 2019.
↑ 1 2 Berlekamp ER Factorizarea polinoamelor peste câmpuri finite // The Bell System Technical Journal. - 1967. - Octombrie ( vol. 46 , iss. 8 ). - P. 1853-1859 . — ISSN 0005-8580 . - doi : 10.1002/j.1538-7305.1967.tb03174.x . Arhivat din original pe 17 februarie 2019.
↑ 1 2 3 4 5 Knuth DE Arta programarii pe calculator . - Reading, Massachusetts: Addison-Wesley Publishing Company, 1968. - Vol. 2. - P. 381-390. — 624 p. - ISBN 0-201-03802-1 . Arhivat pe 3 august 2019 la Wayback Machine
↑ Sze TW Despre luarea rădăcinilor pătrate fără nereziduuri pătratice peste câmpuri finite // Matematica calculului. - 2011. - 3 ianuarie ( vol. 80 , iss. 275 ). - P. 1797-1811 . — ISSN 0025-5718 . - doi : 10.1090/s0025-5718-2011-02419-1 .
↑ Peralta R. Un algoritm probabilistic simplu și rapid pentru calculul rădăcinilor pătrate modulo un număr prim (Corresp. ) // IEEE Transactions on Information Theory. - 1986. - Noiembrie ( vol. 32 , iss. 6 ). - P. 846-847 . — ISSN 0018-9448 . - doi : 10.1109/TIT.1986.1057236 . Arhivat din original pe 30 iunie 2019.
↑ Padró C., Sáez G. Taking cube roots in Zm // Applied Mathematics Letters. - 2002. - August ( vol. 15 , iss. 6 ). - P. 703-708 . — ISSN 0893-9659 . - doi : 10.1016/s0893-9659(02)00031-9 .
↑ 1 2 3 Ben-Or M. Algoritmi probabilistici în câmpuri finite // 22th Annual Symposium on Foundations of Computer Science (sfcs 1981). - 1981. - Octombrie. - P. 394-398 . - doi : 10.1109/SFCS.1981.37 . Arhivat din original pe 29 iulie 2019.
↑ Camion P. A Deterministic Algorithm for Factorizing Polynomials of Fq [X] // Combinatorial Mathematics, Proceedings of the International Coloquium on Graph Theory and Combinatorics. - Elsevier, 1983. - P. 149-157 . — ISBN 9780444865120 .
↑ Grenet B., van der Hoeven J., Lecerf G. Deterministic root finding over finite fields using Graeffe transforms // Aplicable Algebra in Engineering, Communication and Computing. - 2015. - Vol. 27 , iss. 3 . — P. 239 . — ISSN 0938-1279 . - doi : 10.1007/s00200-015-0280-5 .
↑ Golomb SW, Hales A., Welch LR Despre factorizarea trinoamelor peste GF(2 ) // Shift Register Sequences. - World Scientific, 2017. - Martie. - 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 Aplicații ale câmpurilor finite . - Springer US, 1993. - P. 22-26. — 218p. - (Seria internațională Springer în inginerie și informatică). — ISBN 9780792392828 . Arhivat pe 30 iunie 2019 la Wayback Machine

Algoritmi teoretici numerelor
Teste de simplitate	Miller Miller - Rabin Luca - Lemaire pepina Agrawala - Kayala - Saxonia Privighetoarea - Strassen
Găsirea numerelor prime	Iterarea peste divizori Sita lui Eratosthenes sita lui Atkin Sieve Sundarama
Factorizarea	Iterarea peste divizori Metoda Fermat p −1 Metoda Pollard Algoritmul ρ al lui Pollard metoda Lehmann Metoda curbei eliptice (algoritmul lui Lenstra) algoritmul lui Dixon Sita pătrată
Logaritm discret	Algoritmul Gelfond-Shanks Algoritmul Polig-Hellman Metoda ρ a lui Pollard Algoritmul Cangurului lui Pollard Algoritmul lui Adleman Algoritmul COS
Găsirea GCD	algoritmul lui Euclid Algoritm avansat Algoritm binar
Modul de aritmetică	Algoritmul lui Montgomery Teorema chineză a restului
Înmulțirea și împărțirea numerelor	Algoritmul Karatsuba Algoritmul Toom-Cook Algoritmul Schönhage-Strassen Algoritmul Fuhrer Algoritmul Harvey-van der Hoeven Algoritmul Burnickel-Ziegler
Calcularea rădăcinii pătrate	Algoritmul Tonelli-Shanks Algoritmul Berlekamp-Rabin