Teoria dei numeri
I numeri primi
La caccia ai numeri primi

I numeri primi fino a 1000
  1   2   3   5   7  11  13  17  19  23  29  31  37
 41  43  47  53  59  61  67  71  73  79  83  89  97
101 103 107 109 113 127 131 137 139 149 151 157 163
167 173 179 181 191 193 197 199 211 223 227 229 233
239 241 251 257 263 269 271 277 281 283 293 307 311 
313 317 331 337 347 349 353 359 367 373 379 383 389
397 401 409 419 421 431 433 439 443 449 457 461 463 
467 479 487 491 499 503 509 521 523 541 547 557 563
569 571 577 587 593 599 601 607 613 617 619 631 641
643 647 653 659 661 673 677 683 691 701 709 719 727
733 739 743 751 757 761 769 773 787 797 809 811 821
823 827 829 839 853 857 859 863 877 881 883 887 907
911 919 929 937 941 947 953 967 971 977 983 991 997 
NB In base alla definizione elementare 1 sarebbe da considerare primo, non avendo altri divisori che se stesso. In teoria dei numeri è però preferibile escluderlo dai numeri primi.
In tal modo i numeri interi positivi vengono a essere divisi in tre insiemi distinti: a) il numero 1; b) i numeri primi; c) i numeri composti (scomponibili in fattori primi).
In matematica l'aggettivo primo è usato in due accezioni leggermente diverse:
Nella tabella a destra sono elencati i numeri primi minori di 1000.
La teoria dei numeri primi nasce intorno al 300AC ad Alessandria con Euclide che negli Elementi riporta alcuni risultati fondamentali:
Pochi anni dopo, sempre ad Alessandria, Eratostene definisce un metodo per trovare la lista di tutti i numeri primi minori di un dato numero N. Questo metodo, noto come il crivello di Eratostene, è tuttora il più efficiente metodo per generare liste di primi.
Da allora non è che si siano fatti molti progressi nella conoscenza dei numeri primi; i risultati più importanti furono ottenuti da Eulero, circa 2000 anni dopo Euclide, con la dimostrazione del teorema di Eulero-Fermat e l'introduzione della funzione di Eulero.
Eulero diede inoltre una nuova e sorprendente dimostrazione dell'infinità dei numeri primi, dimostrazione che un secolo dopo portò Riemann a formulare quella congettura di Riemann che attende ancora oggi una dimostrazione (o una confutazione).
Negli ultimi anni la disponibilità di computer con elevate capacità di calcolo ha permesso di scoprire numeri primi sempre più grandi, ma non ha fatto fare passi avanti alla teoria!

In definitiva sappiamo ancora molto poco sui numeri primi. In particolare:

Il fatto di sapere così poco sui numeri primi si è rivelato un vantaggio per i crittologi; oggi quasi tutti i computer usano per comunicare in modo riservato il cifrario RSA basato appunto sulla difficoltà di scomporre in fattori primi numeri molto grandi (centinaia di cifre decimali).
Se un giorno un matematico dovesse scoprire un metodo per trovare velocemente i fattori primi di un qualsiasi numero, il cifrario RSA perderebbe di colpo tutta la sua sicurezza!
Alcuni ritengono che una chiave del problema sia la congettura di Riemann; se venisse dimostrata potrebbe aprirsi la strada ad algoritmi veloci per la fattorizzazione di un numero qualsiasi. Ma siamo appunto nel campo delle congetture.


Valido HTML 4.01!

Fonti bibliografiche e collegamenti