Seguici su Telegram, ne vale la pena ❤️ ➡ @trovalost
Vai al contenuto

Guida pratica ai numeri primi


Cerchi un hosting economico per il tuo sito o blog? Tophost ti aspetta (clicca qui)

Cosa sono i numeri primi? I numeri primi sono numeri naturali maggiori di 1 che sono divisibili solo per 1 e per se stessi. Lo sappiamo dai tempi della scuola e ce lo ripetiamo a menadito, ma spesso tendiamo a sottovalutare le conseguenze pratiche che questo aspetto ha nella vita di ogni ogni giorno.

Teorema del quoziente e del resto

In matematica esiste il teorema del quoziente e del resto secondo il quale se fissiamo a e b come numeri naturali, per cui a può essere un qualsiasi numero naturale mentre invece b può essere un qualsiasi numero naturale diverso da zero, sarà sempre possibile trovare due numeri numeri q e r, unici, tali che si possono esprimere come il prodotto di b per q più r, con r minore strettamente di b.

Scritto in formule avremo:

q, r N;

a = b × q + r

r < b

Come sappiamo q ed r vengono chiamati quoziente e il resto di a per b. Se r uguale a zero la divisione sarà esatta, mentre invece serve maggiore di zero avrà un resto r.

E a questo punto entrano in gioco i numeri primi: da quello che abbiamo scritto possiamo convenire che ogni numero sia divisibile per uno e per se stesso, dato che si può sempre esprimere come prodotto di uno per a. Ogni numero B sarà diviso divisore di zero dato che B per zero fa sempre zero. Se consideriamo numeri strettamente maggiori di 1, a questo punto, troveremo alcuni numeri che sono multipli solo di uno e di se stessi che vengono detti numeri primi, mentre ce ne saranno altri che ammettono ulteriori divisori che sono detti numeri composti.

Teorema fondamentale dell’aritmetica

Saranno quindi i primi numeri 2,3, 5,7, 11,13, mentre invece saranno numeri composti quattro, 6, 8. 9, 10, 12, esattamente come 365 oppure 996. L’irregolarità della distribuzione tra numeri primi e numeri composti (diversa da quella più netta tra numeri pari e dispari, ad esempio) è sicuramente degna di interesse per i matematici, ma anche per gli informatici che si occupano di crittografia. Per comprendere a questo punto cosa sono davvero numeri numeri primi bisogna considerare la base teorica su cui si fondano i numeri numeri composti, ovvero il teorema fondamentale dell’aritmetica. Senza entrare nei dettagli tecnici della dimostrazione, il teorema afferma che ogni numero naturale strettamente maggiore di uno si può decomporre nel prodotto di fattori primi, e tale rappresentazione non soltanto esiste sempre ma è unica a meno dell’ordine.

In termini più semplici, il teorema afferma che qualsiasi numero naturale (> 1) può essere espresso come il prodotto di numeri primi, e questa rappresentazione è unica, nel senso che se prendi due diverse decomposizioni di un numero naturale nei suoi fattori primi, queste differiranno solo nell’ordine in cui sono scritti i fattori primi.

Ad esempio, prendiamo il numero 60. La sua decomposizione in fattori primi è:

60=2×2×3×5

Questo significa che 60 può essere espresso come il prodotto dei fattori primi 2, 3 e 5. Se provassimo a decomporre 60 in fattori primi in un altro modo, otterremmo ancora gli stessi fattori primi, ma potrebbero essere disposti in un ordine diverso:

60=3×5×2×2

Anche se l’ordine dei fattori primi è diverso, i fattori stessi sono gli stessi: 2, 3 e 5. Questa è l’unicità della decomposizione in fattori primi garantita dal Teorema Fondamentale dell’Aritmetica. Analogamente:

e così via, il che suggerisce che ogni scomposizione in fattori prima sia univoca, una sorta di “codice fiscale” di ogni numero. Secondo il Teorema Fondamentale dell’Aritmetica, ogni numero naturale maggiore di uno ha una sola scomposizione in fattori primi, e questa scomposizione è unica a meno dell’ordine dei fattori.

Quindi, due scomposizioni in fattori primi che rappresentano lo stesso numero devono avere gli stessi fattori primi, anche se possono essere disposti in ordine diverso.

Come determinare se un numero è primo

Storicamente le prime tecniche per determinare il suo numero primo si devono agli antichi greci: l’algoritmo autorizzato era parecchio elementare, in effetti, e consisteva semplicemente nel provare tutti i numeri fino ad arrivare a quello dato. Anche senza conoscere la teoria della complessità computazionale, si noti, è chiaro che è più grande il numero più tempo impiegherà all’algoritmo a concludere le proprie considerazioni.

Ti potrebbe interessare:  Dove trovare le immagini per il tuo blog

Per ogni possibile numero naturale N maggiore di uno:

  1. come primo passo proveremo a dividere N per due, per tre, … per N-1;
  2. non appena una delle divisioni producesse resto zero prenderemo nota del quoziente q, e ricorderemo che può essere espresso come b × q (dove si intende che B sia il valore che abbiamo trovato tra quelli del passo uno);
  3. Se invece tutte le divisioni producessero il resto non nullo concluderemmo che N è effettivamente un numero primo.

Sulla carta semplice, nella pratica (fin dai tempi di Gauss che se ne accorse) molto complesso da mettere in pratica per N molto grande.

Crivello di Eratostene

Il crivello di Eratostene è un antico algoritmo per trovare tutti i numeri primi fino a un certo limite. Questo metodo è stato sviluppato da Eratostene, un matematico greco antico.

In parole semplici, il crivello di Eratostene funziona in questo modo:

  1. Si prende una lista di numeri da 2 fino al limite desiderato.
  2. Si inizia con il primo numero della lista (che è il numero 2) e si cancellano tutti i suoi multipli dalla lista, lasciando solo il 2 e i suoi multipli.
  3. Si passa al prossimo numero nella lista ancora non cancellato (il 3), e si cancellano tutti i suoi multipli dalla lista.
  4. Si continua questo processo fino a quando non si arriva all’ultimo numero nella lista.

Alla fine, rimarranno solo i numeri primi nella lista.

Crivello di Eratostene in Python

In questo codice Python, la funzione crivello_eratostene restituisce una lista di numeri primi fino al limite specificato. Utilizza un approccio simile a quanto descritto sopra: crea una lista di booleani inizializzati a True per indicare che tutti i numeri inizialmente sono considerati primi. Poi, attraverso un doppio ciclo, identifica i numeri non primi impostando a False i loro multipli. Alla fine, restituisce una lista contenente solo i numeri primi trovati.

def crivello_eratostene(limite):
    numeri = [True] * (limite + 1)
    numeri[0] = numeri[1] = False  # 0 e 1 non sono primi
    
    for i in range(2, int(limite ** 0.5) + 1):
        if numeri[i] == True:
            for j in range(i*i, limite + 1, i):
                numeri[j] = False
    
    primi = [num for num in range(2, limite + 1) if numeri[num] == True]
    return primi

# Utilizzo dell'algoritmo con limite 50 come esempio
limite = 50
numeri_primi = crivello_eratostene(limite)
print("Numeri primi fino a", limite, ":", numeri_primi)

Primi 100 numeri primi

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

Tavola dei primi 200 numeri primi

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, 1009, 1013, 1019,
1021, 1031, 1033, 1039, 1049, 1051, 1061, 1063, 1069, 1087, 1091, 1093, 1097, 1103,
1109, 1117, 1123, 1129, 1151, 1153, 1163, 1171, 1181, 1187, 1193, 1201, 1213, 1217, 1223,
1229, 1231, 1237, 1249, 1259, 1277, 1279, 1283, 1289, 1291, 1297, 1301, 1303, 1307, 1319,
1321, 1327, 1361, 1367, 1373, 1381, 1399, 1409, 1423, 1427, 1429, 1433, 1439, 1447, 1451, 1453,
1459, 1471, 1481, 1483, 1487, 1489, 1493, 1499, 1511, 1523, 1531, 1543, 1549, 1553, 1559, 1567

Numeri primi fino a 1000

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

Ti potrebbe interessare:  Email professionale: come e perchè

Approfondimento: numeri primi e crittografia

La crittografia e i numeri primi sono strettamente collegati grazie a concetti come la crittografia asimmetrica e il problema della fattorizzazione.

La crittografia asimmetrica coinvolge l’uso di coppie di chiavi: una chiave pubblica e una chiave privata. Queste chiavi sono legate da proprietà matematiche complesse, spesso basate sulla difficoltà di fattorizzare grandi numeri composti in numeri primi.

Un esempio di ciò è il sistema RSA, che sfrutta il fatto che è relativamente semplice moltiplicare due numeri primi per ottenere un numero composto, ma estremamente difficile, almeno con le tecnologie attuali, fattorizzare un grande numero composto nei suoi fattori primi originali.

La sicurezza del sistema RSA si basa proprio sulla difficoltà computazionale di fattorizzare numeri molto grandi in numeri primi. Più grande è il numero primo usato nella generazione delle chiavi, più difficile diventa per un algoritmo tradizionale trovare i fattori primi e rompere il sistema crittografico.

Esistono altri algoritmi più efficienti per trovare i numeri primi senza esaminare tutte le combinazioni fino a un certo limite, come fa l’approccio se vogliamo “ingenuo” di Eratostene. Un esempio è il “test di primalità di Miller-Rabin” che è più veloce solo per numeri molto grandi. Questo test non esamina tutte le combinazioni, ma si basa su concetti più complessi della teoria dei numeri per identificare se un numero è primo o no. Altri algoritmi come il “crivello quadrato”, ad esempio, sono più efficienti del crivello di Eratostene per numeri molto grandi.

In generale, trovare numeri primi molto grandi è un problema difficile e ci sono continui sviluppi in teoria dei numeri e in informatica per rendere la ricerca dei numeri primi più efficiente, soprattutto quando si tratta di numeri estremamente grandi utilizzati in crittografia e in altre aree della matematica e della scienza computazionale.

Da non perdere 👇👇👇



Questo sito esiste da 4413 giorni (12 anni), e contiene ad oggi 3953 articoli (circa 3.162.400 parole in tutto) e 12 servizi online gratuiti. – Leggi un altro articolo a caso
Non ha ancora votato nessuno.

Ti sembra utile o interessante? Vota e fammelo sapere.

Questo sito contribuisce alla audience di sè stesso.
Il nostro network informativo: Lipercubo.it - Pagare.online - Trovalost.it.