• Berlekamp
• Groebner
• polynomial factorization
• finite fields
• fattorizzazione di polinomi
• campi finiti
• deterministic algorithms
• algoritmi deterministici
• Niederreiter

Uno dei problemi principali nella decodifica dei codici correttori di Reed Solomon consiste nel trovare le radici di un polinomio a coefficienti su un campo finito solitamente di caratteristica 2. Trovare un algoritmo per risolvere questo problema in un modo veloce e deterministico è alla base della progettazione dei circuiti che si preoccupano di correggere il flusso dei dati che può arrivare da dispositivi come lettori CD-ROM, hard-disk e in generale la maggior parte dei canali di comunicazione digitale.

Nel 1967 Berlekamp presentò un semplice algoritmo, ora noto con il suo nome, per la scomposizione di un polinomio su un campo finito. Tramite la risoluzione di un'opportuna equazione lineare, definita equazione di Berlekam, si trovavano dei polinomi che ci aiutano nel processo di fattorizzazione.

L'algoritmo di Berlekamp è rimasto a lungo l'unica scelta possibile per scomporre un polinomio. Un notevole risultato si è ottenuto nel 1981 con l'algoritmo di Cantor-Zassenhaus. Tuttavia tale algoritmo non è deterministico. Questo potrebbe causare dei problemi nel caso dell'implementazione dell'algoritmo su di un circuito, dato che, dovendolo riapplicare costantemente per la correzione dei dati che giungono da un certo canale, vorremmo un limite sicuro sul tempo massimo che l'algoritmo impiega per fattorizzare il polinomio dato.

Nel 1993 Niederreiter inventò un nuovo algoritmo molto simile a quello di Berlekamp che si basava sulla risoluzione di una diversa equazione differenziale. Le soluzioni di tale equazione possono essere utilizzate allo stesso modo di quelle per l'equazione di Berlekamp per produrre delle scomposizioni. Ci si è resi conto velocemente che da una soluzione per la prima equazione ci si poteva facilmente ricondurre a una soluzione per la seconda e viceversa. Tuttavia le due equazioni sono molto diverse fra loro e possono risultare l'una più semplice da risolvere dell'altra in casi diversi.

Studiando l'equazione di Niederreiter ci siamo accorti che era possibile un'applicazione di un'idea sviluppata nel 1994 per il cambio di ordinamento di una base di Groebner per ideali zero dimensionali che avrebbe potuto velocizzare di molto la procedura di calcolo delle soluzioni. Anche in questo caso il potente strumento delle basi di Groebner si è rivelato vincente e uno studio approfondito dell'algoritmo prodotto ci ha fornito un limite superiore sul numero delle operazioni richieste per trovare le soluzioni notevolmente inferiore rispetto al metodo diretto di risoluzione lineare dell'equazione. Anche se all'apparenza sembrava meno evidente di come invece lo era per l'equazione di Niederreiter, ci siamo resi conto che, con un semplice conto algebrico, era possibile ricondurre l'equazione di Berlekamp ad una forma sulla quale applicare il nuovo algoritmo.

Tale algoritmo ha una grande importanza dal punto di vista teorico per il semplice motivo che è deterministico mentre la maggior parte degli algoritmi noti che si applicano allo stesso problema sono di natura probabilistica. Tuttavia abbiamo voluto verificarne la validità pratica effettuando delle prove sperimentali. A tal fine abbiamo implementato l'algoritmo in un programma scritto in C++ che fa uso della libreria per polinomi su campi finiti NTL di Victor Shoup, reperibile al sito www.shoup.net. I risultati osservati si sono rivelati molto interessanti e dimostrano che, nel caso di polinomi dello stesso tipo di quelli da fattorizzare nell'ambito dei codici di Reed Solomon, l'algoritmo è competitivo anche rispetto ad altri algoritmi di fattorizzazione probabilistici.

All'interno della tesi mostreremo delle tabelle comparative che mettono a confronto il nostro algoritmo con quelli sviluppati originariamente da Berlekamp e da Niederreiter e con quello di Cantor-Zassenhaus già incluso nella libreria NTL. Il codice del programma usato è liberamente consultabile ed è incluso per completezza.