Test di primalità probabilistici e deterministici

Laurea in Informatica

 

La matematica si è sempre interessata allo studio dei numeri primi, cercando di evidenziarne le proprietà e accentuarne le differenze con gli altri numeri inteti, detti composti.

Oggi, molte di queste caratteristiche sono ancora da formalizzare e rimangono delle congetture. Recentemente è stato risolto un problema, noto in letteratura come "PRIMES" e che consiste nel trovare un algoritmo efficiente per testare la primalità di un numero. In realtà, l'interesse sull'efficienza computazionale si è diffuso solo negli anni sessanta con l'avvento dei calcolatori elettronici, ma da parecchi secoli, i matematici si sono cimentati nella produzione di algoritmi di primalità più o  meno veloci.

 

 

 

Scarica la tesi

http://www.matematicamente.it//tesi/Durso-Test_primalita.pdf

 

Commenti

commenti

Ci sono 4 commenti su questo articolo:

  1. grazie mille, devo fare un lavoro per un corso a riguardo e mi è tornata utile la tua tesi! concordo con la critica riguardo certi tabù da informatici che non dovrebbero esistere. ciao!

  2. Caro Giancarlo,sono molto interessato all’algoritmo AKS,ma non potendo stampare il documento non riesco ad apprezzare i contenuti leggendo solamente il testo sul monitor del computer..non potresti rendere disponibile la stampa? Grazie anticipatamente.

  3. Io proverei a non fare allarmismi, almeno per il crivello di eratostene! Si è vero che c’è un errore : la riga j = j+1 andrebbe sostituita con j = j+i. Però se c’è un errore di distrazione….mica cade l’universo! Infatti la dimostrazione del crivello è correta ed è basata su j=j+i. La tesi, come hai visto, non prevedeva l’implementazione di Eratostene (che ho fatto solo adesso in 1 minuto e funziona!!!). Non nego di aver trovato tante difficoltà, sia io che il mio relatore abbiamo ragionato su tanti concetti…soprattutto sull’algoritmo AKS. Ecco immagina lo stato in cui ho dovuto lavorare: Nelle facoltà italiane di informatica, questi argomenti sono TABU’ come se la vera informatica è saper smanettare un PC, montare e smontare computer (cosa che sicuramente un teeneger saprà fare meglio di me). In tanti mesi ho affrontato un argomento per me difficile (perchè non ho la preparazione di un matematico), ho dimostrato da solo piccoli risultati, scrivermi la tesi in latex (molti affidano la stesura a terzi…ma io a chi l’affidavo, se la gente sa usare solo Word?) e per chiudere in bellezza, tentare una difficile implementazione di AKS. Non parliamo della bibliografia…un teorema qui un teorema là…se avessi dovuto ordinare tutti i libri non so quanto mi sarebbe costata questa tesi. Quindi ho lavorato con articoli e paper sparsi su internet per risparmiare! Ho letto anche 1 articolo in giapponese (che ovviamente ho capito solo dai passaggi matematici). Per chiudere il lavoro e non rimanere ancora altri mesi nell’approfondire tutto il feedback matematico, ho troncato degli argomenti inserendo solo dei risultati già noti e provati dalla comunità scientifica, ma non dimostrandoli nella mia tesi. Io starei più attento a valutare questo lavoro (anche se ci possono essere degli errori concettuali). Ma ripeto, molti, questo lavoro, …non lo avrebbero neanche iniziato! ed è facile, adesso, leggere la tesi in 4 giorni bella pronta, in italiano, con una preparazione matematica alle spalle, con i teoremi ordinati, e magari dire che ci sono errori.

  4. Caro Giancarlo,
    sto leggendo la tua tesi perchè sono interessata ad un articolo sull’algoritmo di Lenstra. Devo però farti una critica:nella stesura ci sono molti errori di battitura e fin qui niente di grave…..ma anche molti di concetto; il più eclatante è quello dell’algoritmo del crivello di eratostene;ma non ti sei accordo che l’algoritmo non funziona?noi matematici veniamo sempre attaccati perchè rimaniamo sul teorico e facciamo poca pratica, ma tu se non sbaglio sei un informatico:quell’algoritmo l’avrai provato suppongo…o no?non voglio essere troppo dura, però mi sembra strano che leggendo la tua tesi in quattro giorni abbia trovato un bel pò di errori e tu che ci avrai lavorato mesi e mesi non te ne sei accorto. come mai?forse l’hai scritta di fretta. Mi dispiace aver messo questo post, ma lo ritenevo necessario, visto che la tesi è disponibile su questo sito.
    Spero tu non te la sia presa..
    un saluto