Skip to content

Fattorizzazione in Numeri Primi: Algoritmi Classici e Algoritmo Quantistico di Shor

Informazioni tesi

  Autore: Salvatore Giugliano
  Tipo: Laurea liv.I
  Anno: 2010-11
  Università: Università degli Studi di Napoli - Federico II
  Facoltà: Scienze Matematiche, Fisiche e Naturali
  Corso: Informatica
  Relatore: Aniello Murano
  Lingua: Italiano
  Num. pagine: 112

Per fattorizzazione si intende quel processo di scomposizione di un numero intero nei suoi numeri costituenti chiamati numeri primi. I numeri primi sono numeri divisibili solo per uno e per se stessi. Nel corso della storia hanno affascinato molte personalità dell'ambiente scientifico e non solo. La sequenza dei numeri primi è molto irregolare, non è possibile stabilire a priori il numero primo successivo, e per qualsiasi matematico che cerca sempre un ordine in Natura, è una questione alquanto intrigante.

Un determinato numero può essere primo oppure composto, ossia risulta essere il prodotto di due o più numeri primi. Determinare i numeri primi che compongono un numero composto è un'operazione non sempre facile. Solo negli ultimi decenni, con l'avvento di Internet, c'è stata una vera e propria riscoperta di questa tematica. Questo rinnovato interesse per i numeri primi e per la fattorizzazione è dovuto al fatto che la sicurezza informatica, sia nelle comunicazioni telematiche che nella protezione dei dati, è basata proprio sui numeri primi e sulla difficoltà che si ha nel processo di fattorizzazione dei numeri composti. Se tali numeri fossero facili da fattorizzare non esisterebbe nessun tipo di sicurezza basato su questi principi.

Procedure che hanno come scopo quello di ricercare i numeri primi di uno specifico numero composto si sono evolute drasticamente nel corso degli ultimi anni. Tali procedure o meglio definibili come algoritmi di fattorizzazione, utilizzando una terminologia molto informale, hanno una durata di esecuzione molto elevata e non sono considerati veloci. Questa caratteristica se la si osserva dalla prospettiva della sicurezza informatica è un elemento positivo. Anche se si considera l'algoritmo più evoluto in termini di velocità di esecuzione si hanno molte difficoltà nel portare a termine la fattorizzazione di interi molto grandi.

Gli algoritmi di fattorizzazione trattati in questa tesi sono solo un piccolo esempio di vari metodi che hanno come comune denominatore un grosso limite: hanno bisogno di molte risorse di calcolo e di tempo esecutivo. Fino ad ora non si è riusciti ad escogitare un algoritmo che riuscisse a fattorizzare qualsiasi grande numero composto in poco tempo. I computer di oggi hanno raggiunto una potenza di calcolo impressionante ma nonostante questa potenzialità la fattorizzazione rimane un problema che si riesce a risolvere soltanto con tempi molto lunghi.

Una soluzione al problema della fattorizzazione potrebbe essere quella di sfruttare un nuovo tipo di calcolo basato sulla fisica quantistica. La fisica o meccanica quantistica può essere utilizzata per avere una drastica accelerazione nella risoluzione di problemi come quello della fattorizzazione. La computazione quantistica si differenzia da quella “classica” per alcune caratteristiche che suonano come controintuitive. Ad esempio la possibilità di avere un bit (anche se si parlerà di bit quantistici) in due stati nello stesso istante, in altre parole si può avere lo stato 0 e lo stato 1 nello stesso momento. Un altro fenomeno molto particolare è l'esecuzione di due o più operazioni in maniera simultanea. Inoltre c'è una singolare caratteristica nei registri con bit quantistici: l'esistenza di una correlazione tra i vari bit. Tale computazione per il momento non ha un riscontro fisico concreto (hardware utilizzabile), è un modello di calcolo teorico e come tale è stato analizzato.

Un interessante sviluppo nella computazione quantistica è stata la creazione dell'algoritmo di fattorizzazione di Peter Shor. Tale algoritmo è l'unico metodo che riesce a determinare i fattori primi di un numero in tempi più rapidi di qualsiasi altro algoritmo classico (secondo stime teoriche). L'algoritmo di Shor è costituito da un insieme di passi classici, in termini computazionali, e da una parte quantistica. Quest'ultima parte è quella fondamentale ma necessita di un calcolatore quantistico per essere eseguita. Per ovviare a questo problema si è utilizzato un programma che riproducesse la computazione quantistica, quindi l'algoritmo di Shor, in un normale computer. Tale programma prende il nome di simulatore o emulatore.

La simulazione dell'algoritmo di Shor riguarda l'intera computazione quantistica, ossia che ogni passo del metodo di Shor è stato riprodotto in un sistema classico come se fosse eseguito su un sistema quantistico. Attraverso questo procedimento si è analizzato il tempo di esecuzione del passo quantistico dell'algoritmo. E' importante sottolineare che la riproduzione di un sistema quantistico all'interno di un ambiente classico non è soddisfacente, nel senso che i molteplici fenomeni quantistici non possono essere riproposti in un normale calcolatore. Tale processo ha come effetto un ampio rallentamento della parte quantistica nell'esecuzione dell'algoritmo di Shor ma si potrà constatare come il passo quantistico è quello che occupa il maggior tempo di esecuzione dell'intera elaborazione dell'algoritmo.

CONSULTA INTEGRALMENTE QUESTA TESI

La consultazione è esclusivamente in formato digitale .PDF

Acquista

CONSULTA INTEGRALMENTE QUESTA TESI

La consultazione è esclusivamente in formato digitale .PDF

Acquista

FAQ

Per consultare la tesi è necessario essere registrati e acquistare la consultazione integrale del file, al costo di 29,89€.
Il pagamento può essere effettuato tramite carta di credito/carta prepagata, PayPal, bonifico bancario, bollettino postale.
Confermato il pagamento si potrà consultare i file esclusivamente in formato .PDF accedendo alla propria Home Personale. Si potrà quindi procedere a salvare o stampare il file.
Maggiori informazioni
Ingiustamente snobbata durante le ricerche bibliografiche, una tesi di laurea si rivela decisamente utile:
  • perché affronta un singolo argomento in modo sintetico e specifico come altri testi non fanno;
  • perché è un lavoro originale che si basa su una ricerca bibliografica accurata;
  • perché, a differenza di altri materiali che puoi reperire online, una tesi di laurea è stata verificata da un docente universitario e dalla commissione in sede d'esame. La nostra redazione inoltre controlla prima della pubblicazione la completezza dei materiali e, dal 2009, anche l'originalità della tesi attraverso il software antiplagio Compilatio.net.
  • L'utilizzo della consultazione integrale della tesi da parte dell'Utente che ne acquista il diritto è da considerarsi esclusivamente privato.
  • Nel caso in cui l'Utente volesse pubblicare o citare una tesi presente nel database del sito www.tesionline.it deve ottenere autorizzazione scritta dall'Autore della tesi stessa, il quale è unico detentore dei diritti.
  • L'Utente è l'unico ed esclusivo responsabile del materiale di cui acquista il diritto alla consultazione. Si impegna a non divulgare a mezzo stampa, editoria in genere, televisione, radio, Internet e/o qualsiasi altro mezzo divulgativo esistente o che venisse inventato, il contenuto della tesi che consulta o stralci della medesima. Verrà perseguito legalmente nel caso di riproduzione totale e/o parziale su qualsiasi mezzo e/o su qualsiasi supporto, nel caso di divulgazione nonché nel caso di ricavo economico derivante dallo sfruttamento del diritto acquisito.
  • L'Utente è a conoscenza che l'importo da lui pagato per la consultazione integrale della tesi prescelta è ripartito, a partire dalla seconda consultazione assoluta nell'anno in corso, al 50% tra l'Autore/i della tesi e Tesionline Srl, la società titolare del sito www.tesionline.it.
L'obiettivo di Tesionline è quello di rendere accessibile a una platea il più possibile vasta il patrimonio di cultura e conoscenza contenuto nelle tesi.
Per raggiungerlo, è fondamentale superare la barriera rappresentata dalla lingua. Ecco perché cerchiamo persone disponibili ad effettuare la traduzione delle tesi pubblicate nel nostro sito.
Scopri come funziona

DUBBI? Contattaci

Contatta la redazione a
[email protected]

Ci trovi su Skype (redazione_tesi)
dalle 9:00 alle 13:00

Oppure vieni a trovarci su

Parole chiave

computazione quantistica
fattorizzazione
numeri primi
shor
algoritmi di fattorizzazione

Non hai trovato quello che cercavi?


Abbiamo più di 45.000 Tesi di Laurea: cerca nel nostro database

Oppure consulta la sezione dedicata ad appunti universitari selezionati e pubblicati dalla nostra redazione

Ottimizza la tua ricerca:

  • individua con precisione le parole chiave specifiche della tua ricerca
  • elimina i termini non significativi (aggettivi, articoli, avverbi...)
  • se non hai risultati amplia la ricerca con termini via via più generici (ad esempio da "anziano oncologico" a "paziente oncologico")
  • utilizza la ricerca avanzata
  • utilizza gli operatori booleani (and, or, "")

Idee per la tesi?

Scopri le migliori tesi scelte da noi sugli argomenti recenti


Come si scrive una tesi di laurea?


A quale cattedra chiedere la tesi? Quale sarà il docente più disponibile? Quale l'argomento più interessante per me? ...e quale quello più interessante per il mondo del lavoro?

Scarica gratuitamente la nostra guida "Come si scrive una tesi di laurea" e iscriviti alla newsletter per ricevere consigli e materiale utile.


La tesi l'ho già scritta,
ora cosa ne faccio?


La tua tesi ti ha aiutato ad ottenere quel sudato titolo di studio, ma può darti molto di più: ti differenzia dai tuoi colleghi universitari, mostra i tuoi interessi ed è un lavoro di ricerca unico, che può essere utile anche ad altri.

Il nostro consiglio è di non sprecare tutto questo lavoro:

È ora di pubblicare la tesi