The Extended Riemann Hypothesis and its Consequences on Primality Tests

Questa tesi ha come scopo quello di fornire una introduzione al test di primalità probabilistico di Solovay-Strassen, che negli anni 60 è stato un punto di partenza fondamentale per gli algoritmi di primalità usati tutt'oggi, e studiarne la connessione con l'ipotesi estesa di Riemann. Il primo capitolo si concentrerà sul fornire al lettore alcuni strumenti fondamentali nello studio della teoria dei numeri, come i simboli di Legendre e i caratteri di Dirichlet. Questi ultimi verranno ripresi nel secondo capitolo, al fine di introdurre una definizione formale dell'ipotesi di Riemann e della sua generalizzazione che useremo per il resto della tesi. Il terzo capitolo si occuperà del test di primalità di Solovay-Strassen, mostrandone l'utilizzo e le limitazioni, e introdurrà le modifiche proposte per renderlo deterministico. Il quarto e ultimo capitolo dimostrerà che l'ipotesi estesa di Riemann rende deterministico la nuova versione del test, e stabilirà dei maggioranti per il numero di prove da eseguire.