• basi di Gröbner
• F5
• basi involutive
• F4

Negli ultimi anni l'algebra computazionale ha cercato di rispondere ad alcune domande classiche riguardanti l'algebra dei polinomi con metodi algoritmici sempre più efficienti.
Nel 1963 Buchberger nella sua tesi di dottorato riuscì a trovare soluzioni pratiche ad alcuni problemi come: dati due ideali I e J generati rispettivamente da polinomi f_1,..,f_s e g_1,..,g_t a coefficienti in un campo e in n variabili:
come si può verificare se I=J?
come si può controllare se un polinomio $h$ appartiene a I?
esiste una maniera efficiente per trovare le soluzioni del sistema f_1=... = f_s=0?

Buchberger introdusse le cosiddette basi di Gröbner (dal nome del suo relatore) per un ideale polinomiale, ovvero una maniera ``comoda'' di rappresentare l'ideale: con questi strumenti è possibile trovare soluzioni comode e eleganti ai problemi sopra citati.
Un sottoinsieme finito G dell'ideale polinomiale I è una base di Gröbner per I se e solo se il leading term di un qualsiasi elemento di I è divisibile per il leading term di un polinomio in G. Dato che la definizione non è costruttiva, oltre che studiarne le proprietà teoriche, Buchberger propose anche nel suo lavoro un algoritmo per calcolarle, che prende il suo nome.
Negli anni successivi vari miglioramenti furono apportati al codice e di nuovi ne vennero proposti (ad esempio il metodo di Relinearizzazione e XL), in modo da cercare di abbassare gli elevati costi computazionali dell'algoritmo originale.
L'importanza di ricercare algoritmi ottimali per il calcolo di basi di Gröbner risiede anche nella loro utilità in crittografia. Infatti alcuni tipi di attacchi a certi crittosistemi introdotti negli ultimi anni necessitano della risoluzione di sistemi di n equazioni in m incognite.
Alcuni esempi sono un sistema di crittografia a chiave pubblica, chiamato HFE
(nato dalle idee di Patarin, dopo che egli stesso riuscì a rompere il crittosistema proposto da Matsumoto e Imai) e il crittosistema Rijnadel riconosciuto da parte del National Institute of Standards and Technology come standard per il governo degli Stati Uniti.
Patarin lanciò una sfida chiedendo di decrittare un messaggio crittato con HFE (con una chiave a 80 bit), per testarne il livello di sicurezza. Faugère nel 2002 in 96 ore riuscì a romperlo con il suo nuovo algoritmo F5, vincendo i simbolici 500$ di premio.
Nel suo articolo Faugère propone una dimostrazione incompleta per la correttezza di F5, e non ne prova la terminazione.
Nel 2005 Stegers cerca di completare le dimostrazioni di Faugère, riuscendovi solo facendo delle congetture che Gash,tre anni dopo, dimostrò false, provando anche nel suo lavoro la dimostrazione della correttezza di F5.
Invece, la terminazione fu provata solo di alcune varianti dell'algoritmo F5 (come F5C di Eder e F5t di Gash) e per l'algoritmo originale di Faugère il problema rimane ancora oggi aperto.

Un altro metodo per trovare una base di Gröbner di un ideale polinomiale consiste nel ricercarne una base involutiva, che in particolare è una base di Gröbner. Una base involutiva B per un ideale polinomiale I è un insieme finito di polinomi tale che per ogni f nell'ideale esiste un elemento b di B tale che il leading term di b divide involutivamente il leading term di f. La divisione involutiva è definita come generalizzazione della classica divisione tra termini.
La teoria delle basi involutive è nata per studiare sistemi di equazioni alle derivate parziali e molto prima dell'introduzione delle basi di Gröbner.
Nonostante gli algoritmi per trovare basi involutive restituiscano più di quanto effettivamente richiesto, hanno dei costi computazionali competitivi.

Questo lavoro è diviso in cinque capitoli.
Nel primo capitolo introduciamo la teoria delle basi di Gröbner sia per ideali polinomiali che per sottomoduli.
Nel secondo capitolo vediamo due algoritmi per il calcolo delle basi di Gröbner: il classico di Buchberger e il più recente F4.
Nel terzo capitolo descriviamo lo pseudo codice dell'algoritmo F5, proponiamo una dimostrazione di correttezza e introduciamo una variante che ne permetta la terminazione. Mostriamo inoltre che per una certa classe di input l'algoritmo F5 non effettua nessun calcolo superfluo, diversamente da quanto succede per l'algoritmo di Buchberger. Riprendiamo l'algoritmo F4 e ne proponiamo una variazione che sfrutta i risultati ottenuti precedentemente.
Nel quarto capitolo parliamo di divisione involutiva e basi involutive; forniamo la teoria necessaria per poter provare i teoremi di correttezza e terminazione degli algoritmi che calcolano basi involutive di ideali polinomiali.
Infine, testiamo i vari metodi introdotti con un esempio: calcoliamo una base di Gröbner di un ideale polinomiale con il metodo delle basi involutive, usando prima la divisione involutiva di Janet e poi quella di Pommaret e successivamente con l'algoritmo F5 e la variante dell'F4.