Indice articoli

Valutazione attuale: 5 / 5

Stella attivaStella attivaStella attivaStella attivaStella attiva
 
Yoyo




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.

Progresso dei vari sotto-progetti.
 
Applicazioni disponibili
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
 
Problemi conosciuti
WU di test che richiedono fino a 2 GB di RAM ma vengono distribuite solo a chi ha la memoria sufficiente.

Accedi per commentare

Articoli

Guida WSL

Updated
Written on 26/02/2021, 18:14 by boboviz
guida-wslGuida a Boinc su WSL   Su stimolo di un nostro volontario abbiamo provato a far funzionare il client boinc in una macchina virtuale linux (ci sono...

Ultime dal Blog

Written on 03/08/2021, 22:27 by boboviz
foldit-e-alphafoldLa "svolta" AlphaFold è una delle più importanti degli ultimi anni, motivo per cui ho deciso di tradurre l'articolo che parla della sua implementazione in...