Numero primo

Esiste un metodo semplice per trovare una lista di numeri primi. Eratostene lo ha creato. Ha il nome di Setaccio di Eratostene. Cattura i numeri che non sono primi (come un setaccio) e lascia passare i numeri primi.

Il metodo funziona con una lista di numeri e un numero speciale chiamato b che cambia durante il metodo. Mentre si procede con il metodo, si cerchiano alcuni numeri nella lista e si cancellano altri. Ogni numero cerchiato è primo e ogni numero cancellato è composto. All'inizio, tutti i numeri sono semplici: non cerchiati e non cancellati.

Il metodo è sempre lo stesso:

1. Su un foglio di carta, scrivi tutti i numeri interi da 2 fino al numero da testare. Non scrivere il numero 1. Passate al passo successivo.
2. Inizia con b uguale a 2. Vai al passo successivo.
3. Cerchia B nell'elenco. Vai al passo successivo.
4. Partendo da b, conta b in più nella lista e cancella quel numero. Ripeti di contare altri b numeri e di cancellare i numeri fino alla fine della lista. Passa al passo successivo.
• (Per esempio: Quando b è 2, cerchiate 2 e cancellate 4, 6, 8, e così via. Quando b è 3, cerchiate 3 e cancellate 6, 9, 12, e così via. Il 6 e il 12 sono già stati barrati. Cancellali di nuovo).
5. Aumentare b di 1. Passare al passo successivo.
6. Se b è stato cancellato, torna al passo precedente. Se b è un numero della lista che non è stato cancellato, vai al 3° passo. Se b non è nella lista, vai all'ultimo passo.
7. (Questo è il passo finale.) Hai finito. Tutti i numeri primi sono cerchiati e tutti i numeri composti sono barrati

Come esempio, si potrebbe fare questo metodo su una lista di numeri da 2 a 10. Alla fine, i numeri 2, 3, 5 e 7 finiranno cerchiati. Sono numeri primi. 4, 6, 8, 9 e 10 saranno cancellati. Sono numeri composti.

Questo metodo o algoritmo richiede troppo tempo per trovare numeri primi molto grandi. Ma è meno complicato dei metodi usati per i numeri primi molto grandi, come il test di primalità di Fermat (un test per vedere se un numero è primo o no) o il test di primalità Miller-Rabin.

I numeri primi sono molto importanti in matematica e informatica. Alcuni usi nel mondo reale sono dati qui sotto. I numeri molto lunghi sono difficili da risolvere. È difficile trovare i loro fattori primi, quindi il più delle volte, i numeri che sono probabilmente primi sono usati per la crittografia e i codici segreti.

• La maggior parte delle persone hanno una carta bancaria, dove possono ottenere denaro dal loro conto, usando un bancomat. Questa carta è protetta da un codice di accesso segreto. Poiché il codice deve essere tenuto segreto, non può essere memorizzato in chiaro sulla carta. La crittografia è usata per memorizzare il codice in modo segreto. Questa crittografia usa moltiplicazioni, divisioni e la ricerca dei resti di grandi numeri primi. Un algoritmo chiamato RSA è spesso usato in pratica. Utilizza il teorema cinese del resto.

• Se qualcuno ha una firma digitale per la sua e-mail, viene usata la crittografia. Questo fa in modo che nessuno possa falsificare una sua e-mail. Prima della firma, viene creato un valore di hash del messaggio. Questo viene poi combinato con una firma digitale per produrre un messaggio firmato. I metodi usati sono più o meno gli stessi del primo caso.

• Trovare il più grande primo conosciuto finora è diventato una specie di sport. Verificare se un numero è primo può essere difficile se il numero è grande. I più grandi numeri primi conosciuti in qualsiasi momento sono di solito i numeri primi di Mersenne perché il test più veloce conosciuto per la primalità è il test di Lucas-Lehmer, che si basa sulla forma speciale dei numeri di Mersenne. Un gruppo che cerca i numeri primi di Mersenne è qui[1].