Pagina 4 di 7
Elliptic Curve Factorization method
Scopo del progetto
In matematica, il termine "Golomb Ruler" si riferisce ad un insieme di numeri interi, non negativi, tali che nessuna coppia distinta di numeri dell'insieme abbia la stessa differenza. Concettualmente, è simile ad un righello costruito in maniera tale che nessuna coppia di punti misuri la stessa distanza.
Fattorizzazione di numeri interi
E' la ricerca dei numeri primi in cui si può fattorizzare un numero intero (es: 6=3x2). L'Elliptic curve factorization method (ECM) è il metodo più veloce attualmente scoperto per la fattorizzazione. In sostanza il progetto ECM è un wrapper che sostiene svariati sotto-progetti di fattorizazione (OddPerfect, ElevenSmooth, XYYXF e MersennePlusTwo factorization project ).
I progetti matematici di fattorizzazione e ricerca di numeri primi sono interconnessi (il test di primalità và eseguito prima) ma tra i due la fattorizzazione sembra più complessa.
In una dispensa universitaria ho trovato alcuni spunti interessanti su questo problema:
Trovare i fattori di un numero intero grande è una impresa assai ardua, e può essere impossibile con le risorse oggi disponibili. Non si conoscono metodi polinomiali per la fattorizzazione, come invece accade per i test di primalità.
Infatti i migliori algoritmi di fattorizzazione noti sono subesponenziali ovvero, in generale, i tempi di elaborazione sono dell’ordine di 2^radiceterza(ln(n)).
Dunque, se per fattorizzare un numero di 100 cifre occorre un tempo Q, per fattorizzarne uno di 200 il tempo sale a circa 50.000.000 Q, e per 300 arriviamo a 60.000.000.000.000 Q. Se Q è un secondo, per un intero di 100 cifre occorre 1 secondo, per 200 cifre più di un anno e mezzo, per 300 cifre 2 milioni di anni.
Trovare i fattori di un numero intero grande è una impresa assai ardua, e può essere impossibile con le risorse oggi disponibili. Non si conoscono metodi polinomiali per la fattorizzazione, come invece accade per i test di primalità.
Infatti i migliori algoritmi di fattorizzazione noti sono subesponenziali ovvero, in generale, i tempi di elaborazione sono dell’ordine di 2^radiceterza(ln(n)).
Dunque, se per fattorizzare un numero di 100 cifre occorre un tempo Q, per fattorizzarne uno di 200 il tempo sale a circa 50.000.000 Q, e per 300 arriviamo a 60.000.000.000.000 Q. Se Q è un secondo, per un intero di 100 cifre occorre 1 secondo, per 200 cifre più di un anno e mezzo, per 300 cifre 2 milioni di anni.
Progresso dei vari sotto-progetti.
Applicazioni disponibili
Sono disponibili applicazioni per:
Sono disponibili applicazioni per:
- OS Windows 32 e 64 bit
- OS Linux 32 e 64 bit
- OS MAC PPC e Intel
Durata: da 5 a 22 ore (stima del tempo di elaborazione su un Q6600)
RAM: 1 MB
Deadline: da 5 giorni
Deadline: da 5 giorni
Problemi conosciuti
WU di test che richiedono fino a 2 GB di RAM ma vengono distribuite solo a chi ha la memoria sufficiente.
WU di test che richiedono fino a 2 GB di RAM ma vengono distribuite solo a chi ha la memoria sufficiente.