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