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].

Dato un polinomio ${\displaystyle f(x)}$ di grado ${\displaystyle n}$ a coefficienti nel campo di Galois ${\displaystyle \mathbb {F} _{q}}$ e che sia privo di fattori ripetuti, si cerca un polinomio ${\displaystyle q(x)\in \mathbb {F} _{q}[x]}$ che divida ${\displaystyle f(x)}$. Ripetendo poi il procedimento per i fattori di ${\displaystyle f(x)}$ così ottenuti, è possibile ottenere la fattorizzazione di ${\displaystyle 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 ${\displaystyle f(x)}$ appartengono sicuramente all'anello quoziente ${\displaystyle R={\frac {\mathbb {F} _{q}[x]}{\langle f(x)\rangle }}}$; l'algoritmo si focalizza sulla ricerca dei polinomi ${\displaystyle g(x)\in R}$ che soddisfano la congruenza

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

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

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

che è una fattorizzazione di ${\displaystyle f(x)}$. Va però osservato che non tutti i fattori della produttoria sono non banali (ovvero elementi invertibili o multipli di ${\displaystyle f(x)}$), ma al variare di ${\displaystyle g(x)}$ e ${\displaystyle s}$ qualcuno lo è sicuramente, a meno che ${\displaystyle 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 ${\displaystyle n\times n}$ a coefficienti in ${\displaystyle \mathbb {F} _{q}}$. Tale matrice, che indicheremo con ${\displaystyle {\mathcal {Q}}}$, è così costruita: l'elemento ${\displaystyle q_{i,j}}$ nell'${\displaystyle i}$-esima riga e ${\displaystyle j}$-colonna è il coefficiente del monomio di grado ${\displaystyle j-1}$ del polinomio ${\displaystyle x^{(i-1)q}}$^[2] modulo ${\displaystyle f(x)}$, ovvero:

${\displaystyle 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 ${\displaystyle g(x)=g_{n-1}x^{n-1}+\ldots +g_{1}x+g_{0}\in R}$ si associa in modo biiettivo il vettore riga ${\displaystyle {\bar {g}}=(g_{0},g_{1},\ldots ,g_{n-1})}$, è relativamente semplice provare che il vettore ${\displaystyle {\bar {g}}{\mathcal {Q}}}$ corrisponde al polinomio ${\displaystyle g(x)^{q}}$ modulo ${\displaystyle f(x)}$. Ne segue che un polinomio ${\displaystyle g(x)\in R}$ appartiene alla sottoalgebra di Berlekamp se e solo se ${\displaystyle {\bar {g}}}$ è un autovettore di ${\displaystyle {\mathcal {Q}}}$, ovvero soddisfa il sistema di ${\displaystyle n}$ equazioni in ${\displaystyle n}$ incognite ${\displaystyle {\bar {g}}({\mathcal {Q}}-I)=0}$ (dove ${\displaystyle I}$ è la matrice identità di ordine ${\displaystyle 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 ${\displaystyle f(x)}$ e ${\displaystyle g(x)-s}$ al variare di ${\displaystyle s}$ in ${\displaystyle \mathbb {F} _{q}}$ (per esempio con l'algoritmo di Euclide): ogni polinomio ottenuto è un fattore di ${\displaystyle f(x)}$, eventualmente banale.

Affinché la procedura descritta funzioni, è essenziale l'ipotesi che ${\displaystyle 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 ${\displaystyle f(x)}$ un polinomio e ${\displaystyle f'(x)}$ la sua derivata formale e si calcoli ${\displaystyle g(x)=MCD(f(x),f'(x))}$. Si hanno allora tre casi:

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

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 ${\displaystyle \mathbb {F} _{q}}$, essendo l'insieme dei coefficienti infinito. Non è infatti neppure ovvio che questo problema sia decidibile. Infatti mentre in ${\displaystyle \mathbb {F} _{q}}$ si potrebbe procedere alla fattorizzazione di un polinomio di grado ${\displaystyle n}$ dividendolo per tutti i ${\displaystyle q^{n/2}}$ polinomi di grado minore o uguale a ${\displaystyle n/2}$ (una tecnica del tutto impraticabile, ma corretta almeno dal punto di vista teorico), in ${\displaystyle \mathbb {Z} [x]}$ è necessario applicare un ragionamento più complesso come il metodo di Kronecker. Tuttavia è possibile provare che esistono un primo ${\displaystyle p}$ e un naturale ${\displaystyle n}$ tali per cui fattorizzando ${\displaystyle f(x)}$ sui campi ${\displaystyle \mathbb {F} _{p}}$, ${\displaystyle \mathbb {F} _{p^{2}}}$, ..., ${\displaystyle \mathbb {F} _{p^{n}}}$, si può ottenere una fattorizzazione di ${\displaystyle f(x)}$ anche su ${\displaystyle \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.

• 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