Algoritmul lui Berlekamp

În matematică, algoritmul Berlekamp este un algoritm pentru factorizarea polinoamelor pe un câmp finit inventat de Elwyn Berlekamp în 1967 . Algoritmul constă în principal în construcția unei matrice adecvate care conține coeficienți obținuți pornind de la cei ai polinomului care trebuie luat în calcul și în calculul celui mai mare divizor comun între polinoame. A fost principalul algoritm pentru factorizarea polinoamelor până la realizarea algoritmului Cantor-Zassenhaus în 1981 de la care a fost înlocuit acum în multe aplicații. Cu toate acestea, metoda este încă implementată în multe sisteme de algebră de calcul , inclusiv PARI / GP, de fapt este ușor de implementat, mulți pași pot fi paralelați eficient și impune puține ipoteze asupra polinomului care trebuie luat în considerare ^[1] .

Descrierea algoritmului

Dat fiind un polinom $f(x)$ ${\ displaystyle f (x)}$ $f (x)$ de grad $n$ ${\ displaystyle n}$ $n$ un coeficienți în câmpul Galois $\mathbb {F} _{q}$ ${\ displaystyle \ mathbb {F} _ {q}}$ ${\ mathbb {F}} _ {{q}}$ și care este lipsit de factori repetați, se caută un polinom $q(x)\in \mathbb {F} _{q}[x]$ ${\ displaystyle q (x) \ in \ mathbb {F} _ {q} [x]}$ ${\ displaystyle q (x) \ in \ mathbb {F} _ {q} [x]}$ care împarte $f(x)$ ${\ displaystyle f (x)}$ $f (x)$ . Repetând apoi procedura pentru factorii de $f(x)$ ${\ displaystyle f (x)}$ $f (x)$ obținut în acest mod, este posibil să se obțină factorizarea lui $f(x)$ ${\ displaystyle f (x)}$ $f (x)$ în polinoame ireductibile (care este în esență unic, deoarece fiecare inel de polinoame pe un câmp finit este un domeniu de factorizare unic ).

Factorii $f(x)$ ${\ displaystyle f (x)}$ $f (x)$ aparțin cu siguranță inelului coeficient $R={\frac {\mathbb {F} _{q}[x]}{\langle f(x)\rangle }}$ ${\ displaystyle R = {\ frac {\ mathbb {F} _ {q} [x]} {\ langle f (x) \ rangle}}}$ ${\ displaystyle R = {\ frac {\ mathbb {F} _ {q} [x]} {\ langle f (x) \ rangle}}}$ ; algoritmul se concentrează pe găsirea polinoamelor $g(x)\in R$ ${\ displaystyle g (x) \ în R}$ ${\ displaystyle g (x) \ în R}$ care satisfac congruența

g(x)^{q}\equiv g(x){\pmod {f(x)}}.

{\ displaystyle g (x) ^ {q} \ equiv g (x) {\ pmod {f (x)}}.}

{\ displaystyle g (x) ^ {q} \ equiv g (x) {\ pmod {f (x)}}.}

Astfel de polinoame formează o subalgebră a $R.$ ${\ displaystyle R}$ $R.$ (văzut ca un spațiu vectorial de dimensiune $n$ ${\ displaystyle n}$ $n$ pe $\mathbb {F} _{q}$ ${\ displaystyle \ mathbb {F} _ {q}}$ ${\ mathbb {F}} _ {q}$ ), numită subalgebra lui Berlekamp . Interesul pentru această subalgebră constă în faptul că fiecare polinom $g(x)\in R$ ${\ displaystyle g (x) \ în R}$ ${\ displaystyle g (x) \ în R}$ satisface identitatea

f(x)=\prod _{s\in \mathbb {F} _{q}}MCD(f(x),g(x)-s),

{\ displaystyle f (x) = \ prod _ {s \ in \ mathbb {F} _ {q}} MCD (f (x), g (x) -s),}

{\ displaystyle f (x) = \ prod _ {s \ in \ mathbb {F} _ {q}} MCD (f (x), g (x) -s),}

care este o factorizare a $f(x)$ ${\ displaystyle f (x)}$ $f (x)$ . Cu toate acestea, trebuie remarcat faptul că nu toți factorii de producție sunt non-banali (adică elemente inversabile sau multipli de $f(x)$ ${\ displaystyle f (x)}$ $f (x)$ ), dar ca $g(x)$ ${\ displaystyle g (x)}$ $g (x)$ Și $s$ ${\ displaystyle s}$ $s$ unele sunt cu siguranță, cu excepția cazului în care $f(x)$ ${\ displaystyle f (x)}$ $f (x)$ nu este ireductibil.

Pentru a construi elementele subalgebrei lui Berlekamp este suficient să construim o bază a acestora ; acest lucru este posibil, deoarece acest sub-cadru este nucleul unei matrice $n\times n$ ${\ displaystyle n \ times n}$ $n \ ori n$ un coeficienți în $\mathbb {F} _{q}$ ${\ displaystyle \ mathbb {F} _ {q}}$ ${\ mathbb {F}} _ {q}$ . Această matrice, pe care o vom indica cu ${\mathcal {Q}}$ ${\ displaystyle {\ mathcal {Q}}}$ ${\ displaystyle {\ mathcal {Q}}}$ , este astfel construit: elementul $q_{i,j}$ ${\ displaystyle q_ {i, j}}$ ${\ displaystyle q_ {i, j}}$ în' $the$ ${\ displaystyle i}$ $the$ -alea linie e $j$ ${\ displaystyle j}$ $j$ -coloana este coeficientul gradului monomial $j-1$ ${\ displaystyle j-1}$ ${\ displaystyle j-1}$ a polinomului $x^{(i-1)q}$ ${\ displaystyle x ^ {(i-1) q}}$ ${\ displaystyle x ^ {(i-1) q}}$ ^[2] modul $f(x)$ ${\ displaystyle f (x)}$ $f (x)$ , adică:

x^{(i-1)q}\equiv q_{i,n}x^{n-1}+\ldots +q_{i,2}x+q_{i,1}{\pmod {f(x)}}.

{\ displaystyle x ^ {(i-1) q} \ equiv q_ {i, n} x ^ {n-1} + \ ldots + q_ {i, 2} x + q_ {i, 1} {\ pmod { f (x)}}.}

{\ displaystyle x ^ {(i-1) q} \ equiv q_ {i, n} x ^ {n-1} + \ ldots + q_ {i, 2} x + q_ {i, 1} {\ pmod { f (x)}}.}

Atunci dacă la orice polinom $g(x)=g_{n-1}x^{n-1}+\ldots +g_{1}x+g_{0}\in R$ ${\ displaystyle g (x) = g_ {n-1} x ^ {n-1} + \ ldots + g_ {1} x + g_ {0} \ în R}$ ${\ displaystyle g (x) = g_ {n-1} x ^ {n-1} + \ ldots + g_ {1} x + g_ {0} \ în R}$ vectorul rând este asociat bijectiv ${\bar {g}}=(g_{0},g_{1},\ldots ,g_{n-1})$ ${\ displaystyle {\ bar {g}} = (g_ {0}, g_ {1}, \ ldots, g_ {n-1})}$ ${\ displaystyle {\ bar {g}} = (g_ {0}, g_ {1}, \ ldots, g_ {n-1})}$ , este relativ ușor să demonstrezi că vectorul ${\bar {g}}{\mathcal {Q}}$ ${\ displaystyle {\ bar {g}} {\ mathcal {Q}}}$ ${\ displaystyle {\ bar {g}} {\ mathcal {Q}}}$ corespunde polinomului $g(x)^{q}$ ${\ displaystyle g (x) ^ {q}}$ ${\ displaystyle g (x) ^ {q}}$ modul $f(x)$ ${\ displaystyle f (x)}$ $f (x)$ . Rezultă că un polinom $g(x)\in R$ ${\ displaystyle g (x) \ în R}$ ${\ displaystyle g (x) \ în R}$ aparține subalgebrei Berlekamp dacă și numai dacă ${\bar {g}}$ ${\ displaystyle {\ bar {g}}}$ ${\ displaystyle {\ bar {g}}}$ este un vector propriu al ${\mathcal {Q}}$ ${\ displaystyle {\ mathcal {Q}}}$ ${\ displaystyle {\ mathcal {Q}}}$ , adică satisface sistemul de $n$ ${\ displaystyle n}$ $n$ ecuații în $n$ ${\ displaystyle n}$ $n$ necunoscute ${\bar {g}}({\mathcal {Q}}-I)=0$ ${\ displaystyle {\ bar {g}} ({\ mathcal {Q}} - I) = 0}$ ${\ displaystyle {\ bar {g}} ({\ mathcal {Q}} - I) = 0}$ (unde este $THE$ ${\ displaystyle I}$ $THE$ este matricea identității ordinii $n\times n$ ${\ displaystyle n \ times n}$ $n \ ori n$ ), care poate fi rezolvat eficient, de exemplu prin aplicarea metodei de eliminare gaussiană , pentru a obține polinoamele căutate.

Odată identificat un polinom cu proprietatea necesară, este suficient să se calculeze cel mai mare divizor comun dintre $f(x)$ ${\ displaystyle f (x)}$ $f (x)$ Și $g(x)-s$ ${\ displaystyle g (x) -s}$ ${\ displaystyle g (x) -s}$ dupa cum $s$ ${\ displaystyle s}$ $s$ în $\mathbb {F} _{q}$ ${\ displaystyle \ mathbb {F} _ {q}}$ ${\ mathbb {F}} _ {q}$ (de exemplu cu algoritmul lui Euclid ): fiecare polinom obținut este un factor de $f(x)$ ${\ displaystyle f (x)}$ $f (x)$ , posibil banal.

Eliminarea factorilor repetați

Pentru ca procedura descrisă să funcționeze, presupunerea că $f(x)$ ${\ displaystyle f (x)}$ $f (x)$ nu au factori repetați. Cu toate acestea, acest lucru nu limitează aplicarea algoritmului, deoarece este posibil să se identifice într-un mod foarte simplu prezența unor astfel de factori folosind proprietățile derivatelor formale . Într-adevăr $f(x)$ ${\ displaystyle f (x)}$ $f (x)$ un polinom e $f'(x)$ ${\ displaystyle f '(x)}$ $f '(x)$ derivatul său formal și se calculează singur $g(x)=MCD(f(x),f'(x))$ ${\ displaystyle g (x) = GCD (f (x), f '(x))}$ ${\ displaystyle g (x) = GCD (f (x), f '(x))}$ . Există apoi trei cazuri:

de sine $g(x)$ ${\ displaystyle g (x)}$ $g (x)$ este o constantă, atunci $f(x)$ ${\ displaystyle f (x)}$ $f (x)$ este lipsit de factori repetați;
de sine $f'(x)=0$ ${\ displaystyle f '(x) = 0}$ $f '(x) = 0$ , asa de $f(x)$ ${\ displaystyle f (x)}$ $f (x)$ este o putere $p$ ${\ displaystyle p}$ $p$ -thth, unde $p$ ${\ displaystyle p}$ $p$ este caracteristica $\mathbb {F} _{q}$ ${\ displaystyle \ mathbb {F} _ {q}}$ ${\ mathbb {F}} _ {q}$ ;
de sine $g(x)$ ${\ displaystyle g (x)}$ $g (x)$ are un grad mai mare de 1, atunci este un factor de $f(x)$ ${\ displaystyle f (x)}$ $f (x)$ .

Factorizarea în inelul numerelor întregi

Algoritmul lui Berlekamp poate fi folosit și în factorizarea polinoamelor cu coeficienți întregi. Această problemă este mult mai dificilă decât cea de factoring in $\mathbb {F} _{q}$ ${\ displaystyle \ mathbb {F} _ {q}}$ ${\ mathbb {F}} _ {q}$ , ansamblul coeficienților fiind infinit. Într-adevăr, nici măcar nu este evident că această problemă este decisivă . De fapt, în timp ce se afla $\mathbb {F} _{q}$ ${\ displaystyle \ mathbb {F} _ {q}}$ ${\ mathbb {F}} _ {q}$ am putea proceda la factorizarea unui polinom de grad $n$ ${\ displaystyle n}$ $n$ împărțind-o la toate $q^{n/2}$ ${\ displaystyle q ^ {n / 2}}$ ${\ displaystyle q ^ {n / 2}}$ polinoame de grad mai mic sau egal cu $n/2$ ${\ displaystyle n / 2}$ $n / 2$ (o tehnică complet impracticabilă, dar corectă cel puțin din punct de vedere teoretic), în $\mathbb {Z} [x]$ ${\ displaystyle \ mathbb {Z} [x]}$ ${\ displaystyle \ mathbb {Z} [x]}$ este necesar să se aplice un raționament mai complex precum metoda Kronecker . Cu toate acestea, este posibil să se demonstreze că există o primă $p$ ${\ displaystyle p}$ $p$ și un firesc $n$ ${\ displaystyle n}$ $n$ astfel pentru care factorizarea $f(x)$ ${\ displaystyle f (x)}$ $f (x)$ pe câmpuri $\mathbb {F} _{p}$ ${\ displaystyle \ mathbb {F} _ {p}}$ ${\ mathbb {F}} _ {p}$ , $\mathbb {F} _{p^{2}}$ ${\ displaystyle \ mathbb {F} _ {p ^ {2}}}$ ${\ displaystyle \ mathbb {F} _ {p ^ {2}}}$ , ..., $\mathbb {F} _{p^{n}}$ ${\ displaystyle \ mathbb {F} _ {p ^ {n}}}$ ${\ mathbb {F}} _ {{p ^ {n}}}$ , o factorizare a $f(x)$ ${\ displaystyle f (x)}$ $f (x)$ de asemenea pe $\mathbb {Z} [x]$ ${\ displaystyle \ mathbb {Z} [x]}$ ${\ displaystyle \ mathbb {Z} [x]}$ . În această formă, metoda se numește algoritmul Berlekamp-Zassenhaus și necesită utilizarea unor observații teoretice mai sofisticate, inclusiv lema lui Hensel .

Notă

^ În algoritmul Cantor-Zassenhaus este de fapt necesar ca polinomul dat să aibă o factorizare în factori de grad egal. Cu toate acestea, această condiție nu limitează câmpul de aplicabilitate al algoritmului, deoarece există metode eficiente pentru determinarea factorizării unui polinom în factori (nu neapărat ireductibili) care au proprietatea necesară.
^ Acordați atenție faptului că rândurile și coloanele din ${\mathcal {Q}}$ ${\ displaystyle {\ mathcal {Q}}}$ ${\ displaystyle {\ mathcal {Q}}}$ sunt numerotate din $1$ ${\ displaystyle 1}$ $1$ la $n$ ${\ displaystyle n}$ $n$ , în timp ce coeficienții polinoamelor de la a $n-1$ ${\ displaystyle n-1}$ $n-1$ .

Bibliografie

Elwyn Berlekamp, Factoring Polynomials Over Finite Fields , în Bell Systems Technical Journal , vol. 46, 1967, pp. 1853–1859.
Donald Knuth , 4.6.2 Factorizarea polinoamelor , în Algoritmi seminumerici , vol. 2, Reading, Addison-Wesley, 1997, ISBN 0-201-89684-2 .

Portalul de matematică : accesați intrările Wikipedia care se ocupă de matematică

[1] În algoritmul Cantor-Zassenhaus este de fapt necesar ca polinomul dat să aibă o factorizare în factori de grad egal. Cu toate acestea, această condiție nu limitează câmpul de aplicabilitate al algoritmului, deoarece există metode eficiente pentru determinarea factorizării unui polinom în factori (nu neapărat ireductibili) care au proprietatea necesară.

[2] Acordați atenție faptului că rândurile și coloanele din ${\mathcal {Q}}$ ${\ displaystyle {\ mathcal {Q}}}$ ${\ displaystyle {\ mathcal {Q}}}$ sunt numerotate din $1$ ${\ displaystyle 1}$ $1$ la $n$ ${\ displaystyle n}$ $n$ , în timp ce coeficienții polinoamelor de la a $n-1$ ${\ displaystyle n-1}$ $n-1$ .

[1]

[2]