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 applicazione. 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 capo 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_1x + 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 (1967). Factoring Polynomials Over Finite Fields. Bell Systems Technical Journal 46: 1853–1859.
• Donald Knuth, 4.6.2 Factorization of Polynomials in Seminumerical Algorithms, Reading, Addison-Wesley, 1997, Vol. 2. ISBN 0201896842

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