Alice, Bob e Eva — Il meraviglioso mondo dei numeri primi

“Cos'è un numero primo?”.

“Un numero che è divisibile solo per sé stesso e per 1”.

“Mh”.

“Cosa?”.

“Quindi 1 è primo?”.

“Eh, sì”.

“Non va mica bene”.

“Perché?”.

“Perché se 1 fosse primo, non potremmo più dire che la scomposizione in fattori primi di un numero è unica. Potremmo mettere tanti fattori 1, e dire per esempio che 10 si scompone in tanti modi diversi: 5·2, oppure 5·2·1, oppure 5·2·1⁴²”.

“Ok, va bene, 1 non è primo. Quindi cos'è un numero primo?”.

“Un numero che ha esattamente 2 divisori distinti può andare?”.

“Sì, mi pare di sì”.

“Comunque basta mettersi d'accordo. Va bene anche la tua definizione, basta escludere 1”.

“Ho capito”.

“Quanti numeri primi ci sono?”.

“Infiniti”.

“Sai dimostrarlo?”.

“Ehm, credo di no”.

“Male! Tutti devono saper dimostrare che ci sono infiniti numeri primi, è uno dei fondamenti della matematica”.

“Eh, vabbè. Dai, come si fa?”.

“Supponi, per assurdo, che siano finiti. Ce ne sono n, e li indichiamo così:”.

p₁, p₂, …, p_n.

“Bene”.

“Ora considera questo numero: p₁p₂…p_n+1. Non sta nella lista, quindi non è primo”.

“Giusto”.

“Per quale p_i è divisibile?”.

“Ah, non lo so”.

“Prova a pensare: è divisibile per p₁? Qual è il resto della divisione per p₁?”.

“Ah, facile, resta 1, l'hai aggiunto tu”.

“Quindi quel numero non è divisibile per p₁. Forse per p₂?”.

“Ah, no, né per p₂ né per nessun altro numero: è come prima, resta sempre 1”.

“Dunque quel numero non ha divisori primi, quindi è primo”.

“Esatto”.

“E questo è assurdo, avevamo detto che non era primo”.

“Ah! È vero! Quindi non è vero che i numeri primi sono finiti. Ok, ho capito”.

“Bene. Ora siamo interessati a trovare dei numeri primi grandi”.

“Perché?”.

“Mah, un Vero Matematico potrebbe risponderti perché esistono”.

“Sì, ok, va bene, non faccio più queste domande”.

“Però potrebbero esserci altri motivi”.

“Mi stai dicendo che servono a qualcosa? Incredibile”.

“Sì, potresti voler cercare numeri primi per la fama, per diventare ricco, oppure per la crittografia”.

“Ricco?”.

“Ah, vedo che il richiamo dei soldi è sempre efficace. Sì, esistono premi per chi scopre numeri primi abbastanza grandi. E naturalmente si viene citati in prestigiose riviste scientifiche, e anche su internet; per questo ho parlato di fama”.

“Uh, sai che bello essere citati su Sorrisi & Equazioni…”.

“Ehm”.

“Comunque, giusto per capire, cosa significa grandi?”.

“Ottima domanda. Vediamo un po': 17 è primo?”.

“Sì”.

“21?”.

“No”.

“E 100001?”.

“Uhm”.

“Problemi?”.

“Ecco, mi servirebbe, ehm…”.

“Una calcolatrice?”.

“Già”.

“Ce la puoi fare ancora senza. Ricordi il criterio di divisibilità per 11?”.

“Ah, giusto, la somma delle cifre di posto pari e quella delle cifre di posto dispari… Ho dei vaghi ricordi. Forse quel numero è divisibile per 11?”.

“Esatto. E cosa mi dici di 100003?”.

“No, qui senza calcolatrice non ce la faccio proprio”.

“Se tu potessi avere una calcolatrice, cosa faresti?”.

“Comincerei a dividere il numero per tutti i numeri primi”.

“Tutti?”.

“Bè, no, fino a 100003. O fino a che non trovo una divisione esatta, naturalmente”.

“Certo. Però 100003 mi sembra tanto, non puoi fermarti prima?”.

“Potrei fermarmi quando arrivo a metà”.

“Ancora troppo. Perché metà? Se scopri che un numero è divisibile per la sua metà, vuol dire che l'altro fattore è 2, e l'avresti già trovato prima”.

“Hai ragione, posso fermarmi quando arrivo a due fattori uguali, cioè alla radice quadrata del numero”.

“Molto bene. Prova”.

“Io provo, ma sono tanti numeri lo stesso”.

“Esatto, sono tanti. Esistono dei programmi per computer che lo fanno in automatico. Prova su questo sito, ad esempio”.

“Ehi, ci ha messo un attimo! E mi ha detto che 100003 è primo, ci avrei messo un po' con la calcolatrice”.

“Infatti. Ora aumentiamo un po'. Pensa a quante operazioni ti servirebbero per scoprire se 10⁵⁰+151 è primo oppure no”.

“Uh, questo è grosso. La radice è dell'ordine di 10²⁵”.

“Ad oggi il processore più veloce fa circa 10¹¹ istruzioni elementari in un secondo. Supponendo che ogni istruzione venga usata per una divisione (e non è così, servono alcune istruzioni elementari per ogni divisione, per non parlare di tutte quelle che servono per tenere in piedi il sistema operativo, ma facciamo finta di niente), dovresti impiegare 10¹⁴ secondi. Sono circa tre milioni di anni”.

“Ehm”.

“Prova il programmino su internet”.

“Abbiamo abbastanza tempo per aspettare? Tre milioni di anni non sono pochi”.

“Prova. Puoi scrivere direttamente l'espressione, quel programmino fa anche i calcoli. Per elevare a potenza puoi usare il simbolo ^”.

“Provo, ok, … ehi, ci ha messo meno di un secondo! Ed è un numero primo! Come ha fatto?”.

“Poi ti spiego. Prima, però, lasciami rispondere a una domanda che hai fatto poco fa: per noi i numeri primi grandi sono dell'ordine di circa 150 cifre. Per i soldi e la fama si parla di 10 milioni di cifre, invece”.

“Wow, ma chi ci riesce a scoprire se un numero di 10 milioni di cifre è primo?”.

“Lo puoi fare anche tu, possono provarci tutti. Il sito www.mersenne.org è il centro di smistamento per una operazione di calcolo distribuito. Chiunque può collegarsi, scaricare il loro programma, farsi assegnare dei numeri da testare e sperare”.

“Ma quanto ci vuole?”.

“Dipende dal computer che hai; comunque quei numeri, che si chiamano numeri di Mersenne, sono numeri speciali per i quali è noto un criterio velocissimo per scoprire se sono primi oppure no. Nel giro di qualche settimana te la cavi. Ogni tanto ne scoprono uno, e assegnano un premio”.

“E come mai a noi bastano numeri di 150 cifre?”.

“Prima di risponderti, ti faccio ancora qualche esempio. Prova a capire se questo numero è primo:”.

12301379934535904458542535439865663519345051820092829408091

“Vediamo… ehi, ci sta mettendo un po'. Dieci secondi: dice che non è primo”.

“Se guardi bene, te lo dice quasi istantaneamente che non è primo. Il resto del tempo lo impiega a scomporlo”.

“Ah, vedo che è composto da solo due fattori. Enormi”.

“Sì, la difficoltà è proprio quella, scoprire i fattori. Nota che il numero è composto da 59 cifre. Fai un'altra prova:”.

100000000000000000000000000000000000000409000000000000000000000000000000000000327

“Però, 82 cifre. Vediamo… ci sta mettendo molto. Un minuto e un po'. Strano”.

“Non ti aspettavi un aumento di tempo così evidente, vero?”.

“Eh, no, con 59 cifre ci ha messo 10 secondi, con 82 più di un minuto”.

“Un'ultima prova: fai un test su questo numero:”.

(10^317-1)/9

“Cosa significa?”.

“È un'espressione che puoi inserire nel programma di fattorizzazione su internet, altrimenti dovresti scrivere un numero composto da 317 cifre 1”.

“Solo cifre 1?”.

“Sì, se svolgi l'espressione (10³¹⁷-1)/9 ottieni un numero composto da 317 cifre tutte uguali a 1”.

“Io ho scritto, ma sta ancora calcolando. Dice che non sa nemmeno se è primo oppure no, mi sa che 317 cifre siano troppe”.

“Lascialo andare, poi guardiamo come va a finire. Intanto, vorrei che tu capissi una cosa: hai visto che il test di primalità è abbastanza veloce, mentre la scomposizione in fattori no”.

“Sì, ho visto”.

“E hai anche visto che, man mano che la lunghezza dei numeri da testare aumenta, aumenta anche il tempo necessario per fare il test”.

“Vedo, sta ancora calcolando”.

“Infatti. E il tempo aumenta non linearmente. Se per fattorizzare un numero di 50 cifre ci metti 10 secondi, per fattorizzarne uno di 100 non ci metti 20 secondi”.

“Ah, no, certo che no, per fattorizzarne uno di 82 ci ha messo ben di più. Mi sa che il calcolo diventi proibitivo quando arriviamo alle 150 cifre di cui avevi parlato”.

“Come sta andando l'analisi del nostro numero da 317 cifre?”.

“Ehi, ha finito, ci ha messo 3 minuti e mezzo! Dice che è un numero primo”.

“Sì, se non fosse stato primo forse sarebbe stato impossibile scomporlo”.

“Ma quindi c'è una notevole differenza tra lo scoprire se un numero è primo e il calcolarne effettivamente i valori”.

“Sì, una differenza immensa, sui cui si basa tutto il concetto della crittografia moderna”.

⇐ · ⇒