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.

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.

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.

Programmazione funzionale in spazio logaritmico: una libreria di funzione aritmetiche

In questa Tesi forniamo una libreria di funzioni aritmetiche che operano in spazio logaritmico rispetto all'input. Partiamo con un'analisi dei campi in cui è necessario o conveniente porre dei limiti, in termini di spazio utilizzato, alla computazione di un determinato software. Vista la larga diffusione del Web, si ha a che fare con collezioni di dati enormi e che magari risiedono su server remoti: c'è quindi la necessità di scrivere programmi che operino su questi dati, pur non potendo questi dati entrare tutti insieme nella memoria di lavoro del programma stesso. In seguito studiamo le nozioni teoriche di Complessità, in particolare quelle legate allo spazio di calcolo, utilizzando un modello alternativo di Macchina di Turing: la Offline Turing Machine. Presentiamo quindi un nuovo “modello” di programmazione: la computazione bidirezionale, che riteniamo essere un buon modo di strutturare la computazione limitata in spazio. Forniamo poi una “guida al programmatore” per un linguaggio di recente introduzione, IntML, che permettere la realizzazione di programmi logspace mantenendo però il tradizionale stile di programmazione funzionale. Infine, per mostrare come IntML permetta concretamente di scrivere programmi limitati in spazio, realizziamo una libreria di funzioni aritmetiche che operano in spazio logaritmico. In particolare, mostriamo funzioni per calcolare divisione intera e resto sui naturali, e funzioni per confrontare, sommare e moltiplicare numeri espressi come parole binarie.

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.

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.

Funzioni BV e disuguaglianze isoperimetriche

All'interno della mia tesi verrà introdotta la teoria delle funzioni in R^{n} a variazione limitata (BV), seguendo le presentazioni di Lawrence C.Evans e Ronald F.Gariepy nel libro Measure Theory and Fine Properties of Functions e di Enrico Giusti nell'opera Minimal Surfaces and Functions of Bounded Variation. Le funzioni BV sono funzioni le cui derivate prime deboli sono misure di Radon, ossia misure di Borel regolari finite sui compatti. In particolare verranno anche analizzati gli insiemi E che hanno perimetro finito, ossia tali che la funzione indicatrice dell’insieme E sia una funzione BV. Nello specifico, nel primo capitolo verranno date le definizioni di funzioni BV e insiemi di perimetro finito, sia in una versione globale che in una locale, verrà enunciato un primo importante teorema per le funzioni BV e verrà analizzata la relazione tra funzioni di Sobolev e funzioni BV. Nel secondo capitolo, invece, verranno analizzate la semicontinuità inferiore, l'approssimazione con funzioni lisce e la compattezza di funzioni BV, mentre nel terzo capitolo verranno elencati alcuni risultati sulle funzioni BV riguardanti la Traccia, l'Estensione e la formula di Coarea. Infine, nel quarto ed ultimo capitolo, verranno studiate le disuguaglianze di Sobolev e Poincaré e le disuguaglianze isoperimetriche per funzioni BV.

Cultura escrita em contextos indígenas

Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES)

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.

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.

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.