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.

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}$ 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:

1. se $g(x)$ è una costante, allora $f(x)$ è privo di fattori ripetuti;
2. se $f'(x)=0$, allora $f(x)$ è una potenza $p$-esima, dove $p$ è la caratteristica di $\mathbb {F} _{q}$;
3. 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.

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.