La fattorizzazione dei numeri primi è al centro dell'attenzione nel settore informatico perché l'algoritmo RSA, il più geniale algoritmo crittografico fin qui scoperto, utilizza una chiave composta da due numeri primi (vedi 98). Se qualcuno scoprisse una fattorizzazione per tale chiave, farebbe saltare in aria o per lo meno metterebbe in grave crisi l'intero sistema mondiale delle trasmissioni protette per l'e-commerce, l'e-banking ed altro.
Il metodo più generale per trovare i fattori primi di un intero resta quello delle divisioni successive, ben noto nelle scuole medie. Il Teorema dei Numeri Primi asserisce che l'insieme dei numeri primi minori o uguali ad n è circa n/log n. Ciò implica che dovremmo eseguire circa 1058 divisioni per scomporre un numero di 200 cifre. Supponendo di avere un supercomputer in grado di eseguire un miliardo di divisioni al secondo impiegando numeri a 60 cifre (roba da fantascienza, almeno ad oggi), impiegheremmo 1041 (miliardi di miliardi di miliardi di miliardi) anni. Tutto questo dà garanzie sull'affidabilità dell'algoritmo RSA, ma lo scenario potrebbe mutare se invece delle brutali divisioni, un metodo sofisticato sfruttasse una qualche proprietà dei numeri primi.
Il primo a stimare l'andamento asintotico dei numeri primi fu Gauss, che valutò la densità dei numeri primi intorno ad n è dell'ordine di:
1/ log n
Da cui deriva la stima dei numeri primi minori o uguali ad n sopra
riportata. Oggi ne sappiamo di più.
Sappiamo ad
esempio che i numeri primi generano delle progressioni aritmetiche di
lunghezza crescente. La seguente tabella riporta le prime sei serie.
Lo studio delle proprietà asintotiche dei numeri primi è oggi di grande attualità. Terence Tao, un giovane matematico che lavora presso la California University, è stato premiato al recente congresso mondiale di matematica tenutosi a Madrid (ICM2006) proprio per un contributo dato in questa direzione.