Questioni elementari di teoria dei numeri

Dopo una breve introduzione storica ci si occupa del problema della dimostrazione della infinità dei numeri primi. Di questa si espongono cinque dimostrazioni diverse trovate nell'arco di più di duemila anni. La tesi è completata dall'esposizione di una serie di criteri di divisibilità utili nell'insegnamento primario e secondario completamente dimostrati.

Alcuni problemi additivi riguardanti i numeri primi

La tesi prende spunto da due laboratori del Piano di Lauree Scientifiche, "Numeri primi e crittografia" e "Giocare con i numeri". Si approfondiscono i problemi additivi riguardanti i numeri primi. Questi sono stati scelti per due principali motivi: la semplicità dei contenuti, che possono essere compresi dagli studenti di tutti i tipi di scuola, e la possibilità di prestarsi bene ad un approccio di tipo laboratoriale da parte degli studenti, adattabile alle diverse preparazioni matematiche e al tempo stesso in grado di stimolare curiosità su problemi ancora irrisolti. Si mostreranno metodi di risoluzione di tipo elementare ma anche metodi che coinvolgono l'analisi complessa.

Il teorema dei numeri primi

In questa tesi si vede una dimostrazione elementare del teorema dei numeri primi. Dopo aver definito le funzioni aritmetiche di Tchebychev theta e psi, si utilizzano le loro proprietà per studiare il comportamento asintotico della funzione di Mertens e infine di pi(x). Inoltre si mostrano alcuni legami tra la zeta di Riemann e la teoria dei numeri e cenni ad altre dimostrazioni del teorema dei numeri primi.

A proposito di Crittografia a chiave asimmetrica e numeri primi: tecniche note e proposta di un nuovo test di primalità euristico e deterministico

Con questa tesi verrà spiegata l'intrinseca connessione tra la matematica della teoria dei numeri e l'affidabilità e sicurezza dei crittosistemi asimmetrici moderni. I principali argomenti trattati saranno la crittografia a chiave pubblica ed il problema della verifica della primalità. Nei primi capitoli si capirà cosa vuol dire crittografia e qual è la differenza tra asimmetria e simmetria delle chiavi. Successivamente verrà fatta maggiore luce sugli utilizzi della crittografia asimmetrica, mostrando tecniche per: comunicare in modo confidenziale, scambiare in modo sicuro chiavi private su un canale insicuro, firmare messaggi, certificare identità e chiavi pubbliche. La tesi proseguirà con la spiegazione di quale sia la natura dei problemi alla base della sicurezza dei crittosistemi asimmetrici oggigiorno più diffusi, illustrando brevemente le novità introdotte dall'avvento dei calcolatori quantistici e dimostrando l'importanza che riveste in questo contesto il problema della verifica della primalità. Per concludere verrà fatta una panoramica di quali sono i test di primalità più efficienti ed efficaci allo stato dell'arte, presentando una nuova tecnica per migliorare l'affidabilità del test di Fermat mediante un nuovo algoritmo deterministico per fattorizzare gli pseudoprimi di Carmichael, euristicamente in tempo O~( log^3{n}), poi modificato sfruttando alcune proprietà del test di Miller per ottenere un nuovo test di primalità deterministico ed euristico con complessità O~( log^2{n} ) e la cui probabilità di errore tende a 0 con n che tende ad infinito.

Eulero, Mascheroni e Riemann costanti ed ipotesi

In questa tesi si descrivono la funzione zeta di Riemann, la costante di Eulero-Mascheroni e la funzione gamma di Eulero. Si riportano i legami tra questi e si illustra brevemente l'ipotesi di Riemann degli zeri non banali della funzione zeta, ovvero l'ipotesi della distribuzione dei numeri primi nella retta dei numeri reali.

La funzione di Möbius di un insieme parzialmente ordinato

Nel 1837 il matematico A.F. Möbius definì la funzione aritmetica mu(n) che vale 0 se n è divisibile per il quadrato di un numero primo, (-1)^k se n è il prodotto di k primi distinti e \mu(1)=1. Essa ricopre un ruolo di fondamentale importanza per quanto riguarda la distribuzione dei numeri primi, nonché per la sua duttilità nella risoluzione di diversi problemi di conteggio grazie alla formula di inversione di Möbius, che può essere pensata come un analogo formale del teorema fondamentale del calcolo integrale. Una sorprendente varietà di problemi di calcolo combinatorio si rivelano essere nient'altro che casi particolari di un problema più generale che riguarda la possibilità di invertire una somma fatta sugli elementi di un insieme parzialmente ordinato. L'obiettivo di questo elaborato è quello di illustrare come sia possibile generalizzare il concetto di funzione aritmetica estendendolo a quello di funzione di un'algebra di incidenza. Le algebre di incidenza hanno catturato l'interesse di svariati matematici a partire dagli anni '60 del secolo scorso, e si svilupparono come ambiente naturale nel quale generalizzare la formula di inversione di Mobius. La funzione di Möbius della teoria dei numeri, definita originariamente sull'insieme dei numeri interi positivi ordinato per divisibilità, può quindi essere definita su generici insiemi parzialmente ordinati.

Il problema della primalità in complessità computazionale

Questa tesi vuole fornire un'introduzione alla complessità computazionale e allo studio dei numeri primi riferito a questa materia. Si tratterà della Macchina di Turing e della sua importanza per calcolabilità e complessità, introducendo le classi P ed NP. Queste saranno approfondite studiando prima la classe di problemi NP-completi e successivamente fornendo alcuni esempi importanti. Nella parte finale ci si occuperà esplicitamente del problema dei numeri primi e si guarderà da vicino l'algoritmo AKS, dimostrandone la correttezza.

Dalla geometria con riga e compasso alla geometria con origami

Lo scopo di questo lavoro è mostrare la potenza della teoria di Galois per caratterizzare i numeri complessi costruibili con riga e compasso o con origami e la soluzione di problemi geometrici della Grecia antica, quali la trisezione dell’angolo e la divisione della circonferenza in n parti uguali. Per raggiungere questo obiettivo determiniamo alcune relazioni significative tra l’assiomatica delle costruzioni con riga e compasso e quella delle costruzioni con origami, antica arte giapponese divenuta recentemente oggetto di studi algebrico-geometrici. Mostriamo che tutte le costruzioni possibili con riga e compasso sono realizzabili con il metodo origami, che in più consente di trisecare l’angolo grazie ad una nuova piega, portando ad estensioni algebriche di campi di gradi della forma 2^a3^b. Presentiamo poi i risultati di Gauss sui poligoni costruibili con riga e compasso, legati ai numeri primi di Fermat e una costruzione dell’eptadecagono regolare. Concludiamo combinando la teoria di Galois e il metodo origami per arrivare alla forma generale del numero di lati di un poligono regolare costruibile mediante origami e alla costruzione esplicita dell’ettagono regolare.

Storia, sviluppi e applicazioni dei logaritmi.

Scopo della tesi è la trattazione dei logaritmi a partire dalla storia di quest'ultimi, al loro sviluppo, fino ad arrivare alle diverse applicazioni dei logaritmi in svariate discipline. La tesi è strutturata in quattro capitoli, nel primo dei quali si parte analizzando quali istanze teoriche e necessità pratiche abbiano preparato la strada all'introduzione dei logaritmi. Vengono riportati alcuni passi del testo più importante dedicato da Nepero ai logaritmi, Mirifici Logarithmorum Canonis Constructio, la modifica ad opera di Henry Briggs e la diffusione dei logaritmi in gran parte dell' Europa. Nel secondo capitolo viene evidenziato il legame tra i logaritmi e la geometria dell'iperbole per poi passare alla trattazione dei primi studi sulla curva logaritmica. Nel terzo capitolo viene esaminata la controversia tra Leibniz e Bernoulli sul significato da attribuire ai logaritmi dei numeri negativi soffermandosi su come Eulero uscì da una situazione di stallo proponendo una teoria dei logaritmi dei numeri complessi. Nel quarto ed ultimo capitolo vengono analizzati i diversi utilizzi della scala logaritmica ponendo soprattutto l'attenzione sul regolo calcolatore, arrivando infine a mostrare le applicazioni dei logaritmi in altre discipline.