Un numero primo è un numero intero maggiore di 1 i cui unici fattori sono 1 e se stesso. Un fattore è un numero intero che può essere diviso equamente in un altro numero. I primi numeri primi sono 2, 3, 5, 7, 11, 13, 17, 19, 23 e 29. I numeri che hanno più di due fattori sono chiamati numeri composti. Il numero 1 non è né primo né composto.
I numeri primi possono essere utilizzati per una serie di motivi. Ad esempio, alcuni tipi di crittografia utilizzeranno numeri primi.
Per ogni numero primo, ad esempio "p", esiste un numero primo maggiore di p, chiamato p '. Questa dimostrazione matematica, dimostrata nell'antichità dal matematico greco Euclide, convalida il concetto che non esiste un numero primo "più grande". Come l'insieme dei numeri naturali N = {1, 2, 3, ...} procede, i numeri primi generalmente diventano meno frequenti e sono più difficili da trovare in un ragionevole lasso di tempo.
Come determinare se un numero è primo
Un computer può essere utilizzato per testare numeri estremamente grandi per vedere se sono primi. Ma, poiché non c'è limite alla grandezza di un numero naturale, c'è sempre un punto in cui testare in questo modo diventa un compito troppo grande, anche per i supercomputer più potenti. Ad esempio, il più grande numero primo conosciuto nel dicembre del 2018 era di 24,862,048 cifre.
Vari algoritmi sono stati formulati nel tentativo di generare numeri primi sempre più grandi. Ad esempio, supponiamo che "n" sia un numero intero e non sia ancora noto se n sia primo o composto. Per prima cosa, prendi la radice quadrata - o la potenza 1/2 - di n; quindi arrotonda questo numero per eccesso al successivo numero intero più alto e chiama il risultato m. Quindi trova tutti i seguenti quozienti:
qm = n / m
q (m-1) = n / (m-1)
q (m-2) = n / (m-2)
q (m-3) = n / (m-3)
. . .
q3 = n / 3
q2 = n / 2
Il numero n è primo se - e solo se - nessuna delle q, come derivato sopra, sono numeri interi.
Primi di Mersenne e Fermat
Un numero primo di Mersenne è un numero che deve essere riducibile alla forma 2 n - 1, dove n è un numero primo. I primi pochi valori noti di n che producono numeri primi di Mersenne sono dove n = 2, n = 3, n = 5, n = 7, n = 13, n = 17, n = 19, n = 31, n = 61 e n = 89.
Un numero primo di Fermat è un numero di Fermat che è anche primo. Un numero di Fermat F n è della forma 2 m + 1, dove m indica la potenza di 2, cioè m = 2 n, e dove n è un numero intero.
Numeri primi e crittografia
La crittografia segue sempre una regola fondamentale: l'algoritmo - o la procedura effettiva utilizzata - non ha bisogno di essere tenuto segreto, ma la chiave sì. I numeri primi possono essere molto utili per creare chiavi. Ad esempio, la forza della crittografia a chiave pubblica / privata risiede nel fatto che è facile calcolare il prodotto di due numeri primi scelti a caso. Tuttavia, può essere molto difficile e dispendioso in termini di tempo determinare quali due numeri primi sono stati utilizzati per creare un prodotto estremamente grande, quando è noto solo il prodotto.
In RSA (Rivest-Shamir-Adleman), un noto esempio di crittografia a chiave pubblica, i numeri primi dovrebbero essere sempre unici. I numeri primi utilizzati dallo scambio di chiavi Diffie-Hellman e dagli schemi di crittografia DSS (Digital Signature Standard), tuttavia, sono spesso standardizzati e utilizzati da un gran numero di applicazioni.