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 ${𝔽}_q$ e che sia privo di fattori ripetuti, si cerca un polinomio $q(x)\in {𝔽}_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{{𝔽}_q[x]}{⟨f(x)⟩}$; l'algoritmo si focalizza sulla ricerca dei polinomi $g(x)\in R$ che soddisfano la congruenza

$g(x{)}^q\equiv g(x)(\mathrm{mod}f(x)).$

Tali polinomi formano una sottoalgebra di $R$ (visto come spazio vettoriale di dimensione $n$ su ${𝔽}_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 {𝔽}_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 ${𝔽}_q$. Tale matrice, che indicheremo con $𝒬$, è 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}+\dots +q_{i,2}x+q_{i,1}(\mathrm{mod}f(x)).$

Allora se ad ogni polinomio $g(x)=g_{n-1}{x}^{n-1}+\dots +g_{1}x+g_0\in R$ si associa in modo biiettivo il vettore riga $\overline{g}=(g_0,g_1,\dots ,g_{n-1})$, è relativamente semplice provare che il vettore $\overline{g}𝒬$ 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 $\overline{g}$ è un autovettore di $𝒬$, ovvero soddisfa il sistema di $n$ equazioni in $n$ incognite $\overline{g}(𝒬-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 ${𝔽}_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^{\prime }(x)$ la sua derivata formale e si calcoli $g(x)=MCD(f(x),f^{\prime }(x))$. Si hanno allora tre casi:

1. se $g(x)$ è una costante, allora $f(x)$ è privo di fattori ripetuti;
2. se $f^{\prime }(x)=0$, allora $f(x)$ è una potenza $p$-esima, dove $p$ è la caratteristica di ${𝔽}_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 ${𝔽}_q$, essendo l'insieme dei coefficienti infinito. Non è infatti neppure ovvio che questo problema sia decidibile. Infatti mentre in ${𝔽}_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 ${𝔽}_p$, ${𝔽}_{p^2}$, ..., ${𝔽}_{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

• Template:Cita pubblicazione
• Template:Cita libro