Fattorizzazione di polinomi: Algoritmo di Berlekamp-Zassenhaus

Il presente lavoro di tesi analizza l'algoritmo di Berlekamp-Zassenhaus per la fattorizzazione di polinomi nel dominio degli interi. Tale algoritmo si articola in tre fasi principali. La prima: l'algoritmo di Berlekamp per la fattorizzazione modulo p, nel quale si sfruttano le proprietà dei campi finiti e l'endomorfismo di Frobenius per la creazione di una matrice il cui studio risulta essenziale ai fini della decomposizione. La seconda parte: il sollevamento di Hensel per portare tale scomposizione a potenze crescenti di p, mediante importanti relazioni di coprimalità, con approfondimento sui limiti da imporre per accertarsi del suo funzionamento. Infine, la terza e ultima parte: la ricostruzione di Zassenhaus, fase computazionale più onerosa, in cui vengono testate le combinazioni dei fattori modulari per identificare i divisori effettivi in Z. La tesi esplora l'efficienza dell'algoritmo, discutendo il problema della esplosione combinatoria nella fase finale e accennando a varianti moderne, come l'algoritmo LLL (Lenstra-Lenstra-Lovász), che mitigano tale criticità. L'analisi dimostra come Berlekamp-Zassenhaus rimanga uno strumento fondamentale per i moderni sistemi di calcolo simbolico.