Algoritmo di Berlekamp

In matematica l'algoritmo di Berlekamp è un algoritmo per la fattorizzazione di polinomi su un campo finito ideato da Elwyn Berlekamp nel 1967. L'algoritmo consiste principalmente nella costruzione di una opportuna matrice contenente coefficienti ottenuti a partire da quelli del polinomio da fattorizzare e nel calcolo del massimo comun divisore tra polinomi. È stato il principale algoritmo per la fattorizzazione di polinomi fino alla realizzazione dell'algoritmo di Cantor-Zassenhaus nel 1981 da cui è stato ormai soppiantato in molte applicazioni. Tuttavia il metodo è ancora implementato in molti sistemi di algebra computazionale, tra cui PARI/GP, infatti è di semplice realizzazione, molti passaggi possono essere parallelizzati in modo efficiente e impone poche ipotesi sul polinomio da fattorizzare^[1].

Descrizione dell'algoritmo

Dato un polinomio $f(x)$ di grado $n$ a coefficienti nel campo di Galois $\mathbb {F} _{q}$ e che sia privo di fattori ripetuti, si cerca un polinomio $q(x)\in \mathbb {F} _{q}[x]$ che divida $f(x)$ . Ripetendo poi il procedimento per i fattori di $f(x)$ così ottenuti, è possibile ottenere la fattorizzazione di $f(x)$ in polinomi irriducibili (che è essenzialmente unica, poiché ogni anello di polinomi su un campo finito è un dominio a fattorizzazione unica).

I fattori di $f(x)$ appartengono sicuramente all'anello quoziente $R={\frac {\mathbb {F} _{q}[x]}{\langle f(x)\rangle }}$ ; l'algoritmo si focalizza sulla ricerca dei polinomi $g(x)\in R$ che soddisfano la congruenza

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

Tali polinomi formano una sottoalgebra di $R$ (visto come spazio vettoriale di dimensione $n$ su $\mathbb {F} _{q}$ ), detta sottoalgebra di Berlekamp. L'interesse per questa sottoalgebra consiste nel fatto che ogni polinomio $g(x)\in R$ soddisfa l'identità

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

che è una fattorizzazione di $f(x)$ . Va però osservato che non tutti i fattori della produttoria sono non banali (ovvero elementi invertibili o multipli di $f(x)$ ), ma al variare di $g(x)$ e $s$ qualcuno lo è sicuramente, a meno che $f(x)$ non sia irriducibile.

Per costruire gli elementi della sottoalgebra di Berlekamp è sufficiente costruirne una base; ciò è possibile poiché tale sottolagebra è il nucleo di una matrice $n\times n$ a coefficienti in $\mathbb {F} _{q}$ . Tale matrice, che indicheremo con ${\mathcal {Q}}$ , è così costruita: l'elemento $q_{i,j}$ nell' $i$ -esima riga e $j$ -colonna è il coefficiente del monomio di grado $j-1$ del polinomio $x^{(i-1)q}$ ^[2] modulo $f(x)$ , ovvero:

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

Allora se ad ogni polinomio $g(x)=g_{n-1}x^{n-1}+\ldots +g_{1}x+g_{0}\in R$ si associa in modo biiettivo il vettore riga ${\bar {g}}=(g_{0},g_{1},\ldots ,g_{n-1})$ , è relativamente semplice provare che il vettore ${\bar {g}}{\mathcal {Q}}$ corrisponde al polinomio $g(x)^{q}$ modulo $f(x)$ . Ne segue che un polinomio $g(x)\in R$ appartiene alla sottoalgebra di Berlekamp se e solo se ${\bar {g}}$ è un autovettore di ${\mathcal {Q}}$ , ovvero soddisfa il sistema di $n$ equazioni in $n$ incognite ${\bar {g}}({\mathcal {Q}}-I)=0$ (dove $I$ è la matrice identità di ordine $n\times n$ ), che può essere risolto in modo efficiente, ad esempio applicando il metodo di eliminazione di Gauss, per ottenere i polinomi cercati.

Una volta individuato un polinomio con la proprietà richiesta è sufficiente calcolare il massimo comun divisore tra $f(x)$ e $g(x)-s$ al variare di $s$ in $\mathbb {F} _{q}$ (per esempio con l'algoritmo di Euclide): ogni polinomio ottenuto è un fattore di $f(x)$ , eventualmente banale.

Eliminazione dei fattori ripetuti

Affinché la procedura descritta funzioni, è essenziale l'ipotesi che $f(x)$ non abbia fattori ripetuti. Tuttavia questo non limita l'applicazione dell'algoritmo poiché è possibile individuare in modo molto semplice la presenza di tali fattori usando le proprietà delle derivate formali. Sia infatti $f(x)$ un polinomio e $f'(x)$ la sua derivata formale e si calcoli $g(x)=MCD(f(x),f'(x))$ . Si hanno allora tre casi:

se $g(x)$ è una costante, allora $f(x)$ è privo di fattori ripetuti;
se $f'(x)=0$ , allora $f(x)$ è una potenza $p$ -esima, dove $p$ è la caratteristica di $\mathbb {F} _{q}$ ;
se $g(x)$ ha grado maggiore di 1, allora è un fattore di $f(x)$ .

Fattorizzazione nell'anello degli interi

L'algoritmo di Berlekamp può essere utilizzato anche nella fattorizzazione di polinomi a coefficienti interi. Tale problema è molto più difficile di quello della fattorizzazione in $\mathbb {F} _{q}$ , essendo l'insieme dei coefficienti infinito. Non è infatti neppure ovvio che questo problema sia decidibile. Infatti mentre in $\mathbb {F} _{q}$ si potrebbe procedere alla fattorizzazione di un polinomio di grado $n$ dividendolo per tutti i $q^{n/2}$ polinomi di grado minore o uguale a $n/2$ (una tecnica del tutto impraticabile, ma corretta almeno dal punto di vista teorico), in $\mathbb {Z} [x]$ è necessario applicare un ragionamento più complesso come il metodo di Kronecker. Tuttavia è possibile provare che esistono un primo $p$ e un naturale $n$ tali per cui fattorizzando $f(x)$ sui campi $\mathbb {F} _{p}$ , $\mathbb {F} _{p^{2}}$ , ..., $\mathbb {F} _{p^{n}}$ , si può ottenere una fattorizzazione di $f(x)$ anche su $\mathbb {Z} [x]$ . Sotto questa forma il metodo prende il nome di algoritmo di Berlekamp-Zassenhaus e richiede l'uso di osservazioni teoriche più sofisticate, tra cui il lemma di Hensel.

Note

^ Nell'algoritmo di Cantor-Zassenhaus è infatti richiesto che il polinomio dato abbia una fattorizzazione in fattori di grado uguale. Tuttavia questa condizione non limita il campo di applicabilità dell'algoritmo, poiché esistono metodi efficienti per determinare una fattorizzare di un polinomio in fattori (non necessariamente irriducibili) che abbiano la proprietà richiesta.
^ Bisogna fare attenzione al fatto che le righe e le colonne di ${\mathcal {Q}}$ sono numerate da $1$ a $n$ , mentre i coefficienti dei polinomi da $0$ a $n-1$ .

Bibliografia

Elwyn Berlekamp, Factoring Polynomials Over Finite Fields, in Bell Systems Technical Journal, vol. 46, 1967, pp. 1853–1859.
Donald Knuth, 4.6.2 Factorization of Polynomials, in Seminumerical Algorithms, vol. 2, Reading, Addison-Wesley, 1997, ISBN 0-201-89684-2.

Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica

[1] Nell'algoritmo di Cantor-Zassenhaus è infatti richiesto che il polinomio dato abbia una fattorizzazione in fattori di grado uguale. Tuttavia questa condizione non limita il campo di applicabilità dell'algoritmo, poiché esistono metodi efficienti per determinare una fattorizzare di un polinomio in fattori (non necessariamente irriducibili) che abbiano la proprietà richiesta.

[2] Bisogna fare attenzione al fatto che le righe e le colonne di ${\mathcal {Q}}$ sono numerate da $1$ a $n$ , mentre i coefficienti dei polinomi da $0$ a $n-1$ .

[1]

[2]