Penso che uno degli algoritmi più veloci sia il Crivello Quadratico
inventato da Carl Pomerance.
Google di sicuro ti potrà dare un sacco di info a riguardo.
Per quanto riguarda l'uso di grandi numeri in RB dovresti usare uno
di questi plugins gratuiti ma molto ben fatti:
http://homepage.mac.com/delaneyrm/
---
Marco Bambini
http://www.sqlabs.net
http://www.sqlabs.net/blog/
On Jan 4, 2006, at 3:35 PM, Matteo Cortonesi wrote:
Ciao a tutti,
vi scrivo perchè ultimamente mi frullano nella testa un po' di idee
riguardo la fattorizzazione di grandi numeri in fattori primi.
Volevo sentire un po' cosa ne pensate a riguardo...
Conoscete qualche algoritmo particolarmente veloce (magari scritto
in realbasic!)?
È possibile trattare grandi numeri in realbasic?
Realbasic si addice per applicazioni del genere che richiedono
molta performance oppure è una lumaca in confronto a routines
simili scritte in C?
In particolare volevo provare a fattorizzare un numero sfida
dell'RSA-Security... Si tratta di un numero a 576 bit. In forma
decimale:
1881988129206079638386972394616504398071635633794173827007633564229888
5971523466548531906060650474304531738801130339671619969232120573403187
9550656996221305168759307650257059
(174 cifre)
La difficoltà di fattorizzazione di grandi numeri è ciò su cui si
basa RSA... se un giorno si dovessero riuscire a fattorizzare
questi numeri in tempi accettabili RSA cadrebbe (anche se ciò forse
non è vero... perchè basterebbe aumentare la lunghezza della
chiave, che in questo caso è 576bit).
Tutte le chiavi RSA (compreso il numerone incollato sopra) sono il
risultato di due fattori primi. Quindi non occorrebbe un algoritmo
che trova TUTTI i fattori primi di un numerò... basterebbe un
algoritmo che trova un fattore primo, quindi un algoritmo
specifico. Una volta trovato un fattore è facilmente ricavabile
l'altro eseguendo la divisione!
Se tutto ciò fosse possibile si potrebbe pensare a costruire un
insieme di client e server per eseguire il calcolo distribuito e
creare magari un "progettino" come seti at home dot
Grazie,
Matteo
PS: A proposito di algoritmi... Dual-Sort che fine ha fatto? È
ancora con noi il suo creatore? Giusto una curiosità!
|