L'Algoritmo di Berlekamp e una sua applicazione alla teoria dei codici ciclici

Nell’era dell’informazione, i messaggi svolgono un ruolo di fondamentale importanza. I segnali inviati tramite i canali elettronici e non solo sono però soggetti a distorsioni vari tipi; per esempio i messaggi inviati tramite linee telefoniche possono essere distorti da altre fluttuazioni elettromagnetiche, mentre forti campi magnetici sono in grado di danneggiare le informazioni memorizzate su un disco. Il risultato è che il messaggio ricevuto o letto può essere diverso da quello originariamente inviato o memorizzato. Risulta quindi fondamentale sapere se si sono verificati errori nella trasmissione: per farlo, si è pensato di aggiungere un numero di simboli di controllo al messaggio, in modo che gli eventuali errori possano essere rilevati, e addirittura corretti. Lo strumento che ci consente di rilevare questi errori è un particolare tipo di codici lineari, ovvero i codici ciclici, i quali permettono una correzione automatica di alcune alterazioni del messaggio attraverso una tecnica di codifica basata sulla ridondanza. I codici ciclici possono essere rappresentati da particolari polinomi, chiamati generatori, a coefficienti su campi finiti, determinati dai fattori di un speciale polinomio avente grado pari alla lunghezza del codice. Il problema si riduce pertanto alla fattorizzazione di polinomi su campi finiti e alla necessità di trovare un algoritmo in grado di farlo in modo veloce ed efficiente. È facile costruire un algoritmo che, dato in input un polinomio di grado n, lo fattorizzi dividendolo per tutti i possibili irriducibili di grado minore o uguale a n. Un tale algoritmo risulterebbe tuttavia inefficace (e molto lento) anche per campi finiti di piccolo ordine e per gradi bassi. Lo scopo di questa tesi, pertanto, è descrivere l'algoritmo ideato nel 1967 dal matematico statunitense Elwyn Berlekamp, riguardante la fattorizzazione dei polinomi su campi finiti. L'algoritmo, combinando il Teorema di Fermat ed alcuni semplici elementi di algebra lineare, permette di fattorizzare agevolmente (ed in modo efficace) ogni polinomio a coefficienti su un campo finito. Inoltre, grazie alla sua semplice realizzazione e alle poche ipotesi che richiede sul polinomio da fattorizzare, il metodo viene oggi implementato in molti sistemi di algebra computazionale.