Teoria dei numeri - I numeri primi
La caccia ai numeri primi più grandi
Il teorema di Fermat-Eulero - Il cifrario RSA

Un numero si dice primo se divisibile soltanto per se stesso e per uno. I numeri primi sono infiniti ma non ne conosciamo nè una formula di generazione , nè una che ce ne dia infiniti .
Esistono però coppie di numeri (p; p+2 dove p, p+2 sono entrambi primi) detti primi gemelli, del tipo 3 e 5, 5 e 7, 11 e 13, 17 e 19 e così via, il cui insieme di appartenenza non sappiamo se sia finito o infinito.
Un sistema per determinare un numero primo consiste nell'utilizzare la formula di Fermat: Fh = 2(2h)+1per h minore di 4 ,gli altri sono risultati essere composti.
I grandi numeri primi noti sono tutti della forma Mp = 2p - 1 (p primo necessariamente), ma non tutti i numeri di Mersenne (cioè calcolati in questo modo) sono primi.

Numeri primi conosciuti

p 2p -1anno
2 3
5 31
13 8191 1461
17131071 1568
3110 cifre 1772
61 19 cifre 1883
127 39 cifre 1876
521 157 cifre 1952
42531281 cifre1961
112133376 cifre1963
4449713395 cifre1979
1398269420921 cifre1996
3021377909526 cifre1998
209960116320430 cifre2003
30402457 9152052 cifre2005
325826579808358 cifre2006

Il numero primo del 13 Novembre 1996 ed è stato trovato da Joel Armengaud e da George Woltman, ecco le cifre con cui inizia: 814717564.. ed ecco quelle con cui termina: 451315711. Per poterlo leggere tutto fate clic qui .

Nel gennaio 1998 il diciannovenne Roland Clarkson ha trovato un numero primo ancora più grande 23021377 con 909526 cifre.
In seguito sono stati trovati numeri primi sempre più grandi; l'ultimo è 232582657-1 scoperto il 6 settembre 2006.
Si veda il sito The Prime Pages per essere sempre aggiornati in proposito.

Sappiamo che è facile venire a conoscenza in tempi brevi se n è primo o composto, ma i tempi per trovare i fattori crescono fortemente al crescere del numero secondo la seguente tabella (la tabella è tratta da una fonte di molti anni fa; i tempi riportati hanno quindi un valore relativo):

Cifre di nSapere se n è primoTrovare i fattori
5015 sec4 ore
7522 sec104 giorni
10040 sec74 anni
20010 min4*109anni (l'età della terra)
5003 giorni4*1025anni
10001 settimana ecc.

Questa caratteristica è preziosa per la crittografia ed è alla base del cifrario RSA.