Programmazione.it v6.4
Ciao, per farti riconoscere devi fare il login. Non ti sei ancora iscritto? Che aspetti, registrati adesso!
Info Pubblicità Collabora Autori Sottoscrizioni Preferiti Bozze Scheda personale Privacy Archivio Libri Corsi per principianti Forum
Le applicazioni della congettura di Goldbach
Scritto da Luca Domenichini il 10-01-2012 ore 05:29
Seminario Intel
Il problema della riduzione in fattori dei semiprimi è particolarmente sentito nell'ambito delle scienze crittografiche, in particolare nella crittografia asimmetrica a chiave pubblica, e nella teoria dei numeri, relativamente alla generazione di numeri pseudo-casuali. Per dare una piccola infarinatura della questione a chi non sapesse di cosa si sta parlando, voglio ricordare che un numero primo è un numero naturale, maggiore di 1, divisibile solo per 1 e per se stesso. Un numero semiprimo (anche detto biprimo, 2-quasi primo o numero pq), viene invece definito come un numero naturale prodotto di due numeri primi (anche uguali).

Le applicazioni dei numeri semiprimi si basano sul concetto che l'identificazione di due numeri primi molto grandi e del loro prodotto è facile per un elaboratore, mentre il processo inverso (trovare i fattori originali partendo dal prodotto) è talmente complicato che il Governo americano, nel 2007, ha messo in palio premi di centinaia di migliaia di dollari per chi fosse riuscito nell'impresa.

La ricerca di un algoritmo universale per risolvere questa annosa questione matematica/informatica spinge quindi molti ricercatori ad affrontare il problema, dal momento che risolverlo vorrebbe dire riuscire ad aprire parecchi lucchetti virtuali, considerati finora inviolabili. Tra i vari studi, c'è quello di Roger G. Doss, Ph.D. della Northcentral University di Chicago, Illinois, che si basa sulla congettura di Goldbach, così definita perché tuttora indimostrata. Proposto nel 1742 dal prussiano Christian Goldbach, questo assunto afferma che ogni numero pari maggiore di 2 può essere considerato la somma di due numeri primi (anche uguali).

Doss espande questa definizione, dichiarando che ogni numero pari maggiore o uguale a 8 può essere considerato come la somma di due numeri primi distinti. Di conseguenza, dato un qualunque numero pari maggiore o uguale a 8 — chiamiamolo e — è possibile definire la Massima Partizione di Goldbach (maxGB) come il prodotto dei due più grandi numeri primi distinti (p e q) la cui somma è quel numero.
  1. e = p + q

Grazie all'equazione quadratica, e fattorizza in:
  1. n = p * q

Poiché, rappresentando su un grafico l'andamento dei maxGB, si ottiene una curva pressoché perfetta, Doss ha scritto un programma in C++ per approssimarne il valore per un qualunque grande numero. L'algoritmo su cui è basato il programma si fonda su una ricerca binaria, e ha di conseguenza una complessità O(logN).

E' possibile vederne il codice su CodeProject. Secondo i test effettuati, dove i risultati sono stati confrontati con quelli di un altro algoritmo noto (il rho di Pollard), la soluzione proposta da Doss è migliore nell'ambito di numeri naturali a 32 e 64 bit. L'autore propone ora di ampliare il lavoro a numeri più grandi.
Precedente: Un tutorial sulla programmazione degli FPGA (2/2)
Successiva: Visual Analyzer, guida introduttiva all'uso (13/20)
Copyright Programmazione.it™ 1999-2014. Alcuni diritti riservati. Testata giornalistica iscritta col n. 569 presso il Tribunale di Milano in data 14/10/2002. Pagina generata in 0.196 secondi.