Alice, Bob e Eva — Come si può giocare a mental poker

“Ora che abbiamo dimostrato matematicamente l'impossibilità di giocare a mental poker, vediamo come si può negare l'evidenza, dire che la matematica sbaglia, e giocare”.

“Voglio proprio vedere”.

“Una premessa: anche se noi abbiamo sempre visto RSA come sistema di crittografia a chiave pubblica, esso può essere usato anche come sistema classico, in cui io mi tengo segrete entrambe le chiavi, quella pubblica e quella privata, e ne uso una per crittare e l'altra per decrittare”.

“Ah, sì, questo è vero: una chiave chiude e l'altra apre. Mi avevi fatto l'esempio dei lucchetti”.

“Esatto. Inoltre l'esempio dei lucchetti è particolarmente adatto, perché consente di capire un'altra proprietà che useremo per giocare: la proprietà commutativa”.

“Cioè?”.

“Cioè io posso applicare al mio messaggio prima il lucchetto 1, poi il lucchetto 2, in sequenza, poi togliere il lucchetto 1 e, solo alla fine, il 2”.

“Non capisco cosa c'entri la proprietà commutativa”.

“Immagina che io prenda il messaggio, lo inserisca in una busta sigillata, numerata con 1. Poi prendo quella busta e la inserisco in una seconda busta, numerata con 2. Cosa devo fare per leggere il messaggio?”.

“Devi aprire la busta 2 e, poi, la 1”.

“Ecco, grazie alla proprietà commutativa io posso anche aprire prima la 1 e poi la 2. L'esempio delle buste non funziona, ma quello dei lucchetti sì: io metto il mio messaggio in una scatola, e sulla serratura posso applicare quanti lucchetti voglio. Poco importa se applico prima il numero 1 e poi il 2, o viceversa. Allo stesso modo non importa l'ordine che seguo per aprirli”.

“Ah, ho capito. E RSA funziona così?”.

“Sì, perché la codifica tramite RSA prevede che tu elevi il tuo messaggio a un certo esponente. Se vuoi codificare due volte con due chiavi diverse, devi elevare due volte. Questo significa che devi moltiplicare gli esponenti, e la moltiplicazione gode della proprietà commutativa”.

“Giusto”.

“Allora vado con il protocollo per giocare. Prima di tutto Bob prende il mazzo di carte, composto da 52 messaggi e li critta tutti utilizzando la sua chiave B”.

“Una sola chiave?”.

“Sì, non facciamo distinzione tra chiave pubblica e privata: Bob tiene la sua coppia di chiavi segreta, una parte viene usata per crittare e l'altra per decrittare. Invece di parlare di coppia di chiavi, chiamiamo il tutto chiave e rendiamo più lineare tutto il discorso”.

“Ok”.

“Poi, naturalmente, Bob mescola il mazzo, cioè permuta tutti i messaggi come vuole”.

“Ma così non sbircia?”.

“Sì, lui sa l'ordine delle carte, ma vedrai che non importa. Dopo aver mescolato il mazzo, lo invia ad Alice”.

“Quindi a questo punto Alice si trova con 52 messaggi che non riesce a decodificare, mentre Bob sa tutto”.

“Esatto. Ora Alice seleziona cinque carte a caso e le trasmette a Bob. Bob le decritta e ottiene la sua mano”.

“Ah, ok. Alice non può decrittare le carte, quindi non sa cosa ha in mano Bob”.

“Proprio così. Ora Alice seleziona altre cinque carte a caso, e le critta con la sua chiave A, poi le invia a Bob”.

“E Bob non può leggerle, perché Alice le ha crittate!”.

“Esatto. Bob può però togliere il suo lucchetto, grazie alla proprietà commutativa del sistema RSA. Lui decodifica i cinque messaggi inviatigli da Alice, ma non può leggerli perché Alice ha messo su di essi anche la sua chiave”.

“E cosa se ne fa di questi cinque messaggi mezzi decrittati?”.

“Li rispedisce ad Alice, la quale può ora togliere la sua chiave e, finalmente, leggerli: ecco la mano di Alice”.

“Ma è geniale”.

“Se è necessario distribuire altre carte, si ripete la procedura. Alla fine della mano i due giocatori rivelano le loro chiavi, in modo che entrambi possano controllare che l'altro non abbia barato”.

“Bellissimo. Ma, allora, com'è la storia? La dimostrazione di impossibilità è sbagliata?”.

“Ti faccio rispondere dai tre matematici:”.

Initially we proved that the card-dealing problem is insoluble, and then we presented a working solution to the problem. We leave it to you, the reader, the puzzle of reconciling these results. (Hint: each player would in fact be able to determine the other player's hand from the available information, if it were not for the enormous computational difficulty of doing so by “breaking” the code.)

⇐

Alice, Bob e Eva — Perché non si può giocare a mental poker

“Non posso credere che una dimostrazione matematica sia sbagliata”.

“Ma non lo è”.

“Allora non è vero che si riesce a giocare a poker via telefono”.

“E invece lo è. Ti riporto le parole degli autori:”.

We will present two solutions to the problem of playing Mental Poker:

1. A rigorous proof that it is theoretically impossible to deal the cards in a way which simultaneously ensures that the two hands are disjoint and that neither player has any knowledge of the other player's hand (other than that the opponent's hand is disjoint from his).

2. An elegant protocol for dealing the cards that permits one to play a fair game of Mental Poker as desired.

The blatant contradiction between our two results is not due to any tricks or faults in either result. In fact, we will leave to the reader the enjoyable task of puzzling out the differences in the underlying assumptions that account for our seemingly contradictory results.

“Enjoyable task? Questi sono matti”.

“Te l'ho detto che si sono divertiti un sacco, no?”.

“Ma com'è la faccenda, allora? Dice che i due risultati sono apparentemente contraddittori”.

“Sì, vediamo la prima parte, per adesso”.

“Ok”.

“Per semplicità, supponiamo che ci siano solo due giocatori, i soliti Alice e Bob, e un mazzo di tre carte, X, Y e Z”.

“Solo tre?”.

“Ce ne devono essere almeno tre, in modo che sia Alice che Bob non possano conoscere la carta dell'altro”.

“Va bene”.

“Allora, supponiamo che esista un sistema per giocare a poker via telefono. Esso prevederà che vengano scambiati alcuni messaggi lungo la linea telefonica”.

“Quali messaggi?”.

“Non lo sappiamo, non sappiamo ancora se esiste questo sistema, né come è fatto. Immaginiamo che esista, e proviamo a vedere che succede. Supponiamo che alla fine Alice ottenga la carta X e Bob la carta Y: per arrivare a questa situazione si sono prima parlati”.

“Mh, ok, per giocare Alice e Bob devono certamente parlarsi, è l'unica cosa che possono fare col telefono”.

“Bene. Quindi il sistema è composto da un certo numero di messaggi, M₁, M₂, …, M_n. Ora indichiamo con S_A l'insieme delle carte che Alice potrebbe aver ottenuto in seguito allo scambio di quei messaggi”.

“Ma come, non abbiamo detto che ne ottengono una per uno? Alice avrà una carta sola, no?”.

“Sì, certo, una sola. L'insieme S_A contiene però tutte le carte permesse da quell'insieme di messaggi. Magari il protocollo prevede che i due giocatori possano fare scelte casuali, e quindi uno stesso scambio di messaggi potrebbe anche dare luogo a carte diverse”.

“Mh, non mi viene in mente nessun metodo che funzioni così, però capisco che in linea teorica non possiamo dare niente per scontato”.

“Proviamo ad andare avanti: se S_A contiene solo X, allora non è vero che Bob non ha informazioni riguardanti le carte di Alice: in questo caso la sequenza di messaggi determina univocamente le carte di Alice, e quindi Bob sa”.

“Mi pare giusto”.

“Quindi S_A non può contenere soltanto X (che è la carta effettivamente presa da Alice), ma deve contenerne anche qualcun altra: ecco perché dicevo che la sequenza di messaggi deve essere compatibile con più assegnazioni di carte. Se la sequenza di messaggi fosse solo associabile alla carta X, Bob potrebbe scoprire la mano di Alice analizzando proprio tutti i messaggi”.

“Va bene. Quindi?”.

“D'altra parte, se S_A contiene tutte e tre le carte, allora Bob non può avere nessuna carta: qualunque carta egli scelga, potrebbe averla già Alice”.

“Anche questo è vero. Quindi S_A deve contenere due elementi?”.

“Proprio così. Ma anche l'insieme di carte che può ottenere Bob dovrà, per simmetria, avere due elementi. I ruoli di Alice e Bob sono perfettamente simmetrici, se S_A contiene due carte, anche S_B (l'insieme di carte che potrebbero essere assegnate a Bob) ne conterrà due”.

“Ma le carte sono in tutto tre”.

“Esattamente, quindi S_A e S_B devono avere un elemento in comune. Nel nostro esempio è Z, che potrebbe essere assegnata a Alice o a Bob”.

“E questo è un problema?”.

“Eh, questo significa che la sequenza di messaggi M₁, …, M_n è compatibile sia col fatto che Alice ottenga la carta Z, sia che Bob ottenga la stessa carta. Quindi il protocollo non garantisce che Bob e Alice ottengano carte diverse. E dunque il mental poker non è realizzabile. C.V.D.”.

“Ah”.

“La prossima volta vediamo come si può giocare a mental poker”.

“Grrr”.

⇐ · ⇒

Alice, Bob e Eva — Zero Knowledge

“Conoscenza zero?”.

“Sì”.

“E cosa significa?”.

“Significa che io so un segreto, ti dimostro che lo conosco, ma non ti dico qual è”.

“Ma dai. E come è possibile?”.

“Con le conoscenze che possediamo ora, è possibile. Ti faccio un esempio facile, che semplifica un po' le cose, ma che fa capire come funziona il tutto. Si tratta di giocare a testa o croce”.

“Dici il gioco con la moneta?”.

“Sì, si scommette sull'esito del lancio di una moneta. Però ci giochiamo via telefono. Tu sei a un capo del telefono, io all'altro, e naturalmente non ci possiamo vedere. Quindi se io lancio la moneta tu non vedi il risultato”.

“E dovrei fidarmi di quello che mi dici tu?”.

“Sì”.

“Figuriamoci”.

“Ma io devo fare in modo che tu ti possa fidare al di sopra di ogni ragionevole dubbio. Questo significa che io ti devo dimostrare di conoscere il segreto (cioè l'esito del lancio) senza però rivelartelo subito, perché altrimenti tu non puoi scommettere”.

“Ma come fai?”.

“Ci accordiamo su questa procedura: io lancio la moneta, se viene testa genero due numeri primi grandi e congruenti a 1 modulo 4. Se viene croce genero due numeri primi grandi e congruenti a 3 modulo 4”.

“Uhm, perchè?”.

“Ora li moltiplico. Supponi che sia uscita testa: se calcolo il resto della divisione per 4 del prodotto cosa ottengo?”.

“Dunque, hai due numeri congruenti a 1, se li moltiplichi tra loro ottieni due numeri congruenti a 1², cioè ancora 1”.

“Perfetto. Ora supponi che sia uscita croce. Se moltiplichi i due numeri cosa ottieni, questa volta?”.

“Questa volta ottengo un numero congruente a 3², cioè 9. Un momento, 9 è congruente a 1 modulo 4”.

“Esatto. Quindi, sia in un caso che nell'altro il numerone che ottengo è congruente a 1. Te lo trasmetto via telefono”.

“Forse comincio a capire”.

“Appena tu ricevi il numero devi scommettere: testa o croce? Naturalmente analizzando il numero non puoi sapere se è uscita testa o croce, perché puoi, in modo veloce, solo calcolare la sua congruenza modulo 4, ma non fattorizzarlo”.

“Ah, di nuovo il problema della fattorizzazione… Quindi io ricevo il numero, scommetto, e poi tu mi dici quello che è uscito? Come faccio a fidarmi?”.

“Io non ti comunico quello che è uscito, ma ti comunico i due numeri. Tu puoi moltiplicarli e vedere se il loro prodotto è uguale al numerone oppure no. Dopo aver fatto la verifica, puoi calcolare la congruenza modulo 4 dei due numeri: se è uguale a 1 è uscita testa, se invece è 3 allora è uscita croce”.

“Bella roba: ci si riesce, non l'avrei mai detto. Certo che testa o croce è proprio il gioco più facile che ci sia”.

“Se vuoi, si può giocare anche a poker via telefono”.

“Poker? Vuoi dire che si riesce a gestire un mazzo di carte senza poterle vedere?”.

“Certo. Per essere precisi: in un articolo i nostri amici Shamir, Rivest e Adleman prima dimostrano che è matematicamente impossibile giocare a poker via telefono, poi mostrano un protocollo corretto, completo e funzionante per farlo”.

“Cosa? Ma così cadono tutte le mie certezze nei confronti della matematica!”.

“Già. Shamir, Rivest e Adleman devono essersi divertiti un sacco a scriverlo”.

⇐ · ⇒

Alice, Bob e Eva — THE MAGIC WORDS ARE SQUEAMISH OSSIFRAGE

Nel numero di Agosto 1977 di Scientific American, la rubrica Mathematical Games di Martin Gardner aveva il seguente titolo: A new kind of cipher that would take millions of years to break. In essa, Gardner aveva scritto una delle prime descrizioni del sistema di crittografia a chiave pubblica RSA.

Gli inventori di RSA avevano anche preparato una sfida per i lettori: dato il sistema di codifica secondo il quale A = 01, B = 02, e così via fino a Z = 26 e spazio = 00; data la seguente chiave pubblica (n,e):

n = 11438162575788886766923577997614661201021829672124236256256184293
    5706935245733897830597123563958705058989075147599290026879543541,

e = 9007;

dato il testo cifrato

c = 9686961375462206147714092225435588290575999112457431987469512093
    0816298225145708356931476622883989628013391990551829945157815154;

ricavare il testo in chiaro.

Già nel 1976 il matematico Richard Guy scrisse:

“Sarei molto sorpreso se qualcuno riuscisse a fattorizzare numeri delle dimensioni di 10⁸⁰, senza utilizzare forme particolari, nel presente secolo”.

Nel 1977 Rivest, in una lettera a Martin Gardner, stimò che il tempo necessario per fattorizzare un numero di 125 cifre che è il prodotto di due numeri primi di 63 cifre dovesse essere almeno di 40 quadrilioni di anni (qualunque significato diamo alla parola quadrilione, è comunque un sacco di tempo). Tempo calcolato sulla base del miglior algoritmo di fattorizzazione noto all'epoca, e supponendo che un singolo prodotto ab modulo c potesse essere calcolato in un nanosecondo (e questo era fantascienza).

Sicuri del fatto che il loro codice non sarebbe mai stato decrittato, gli inventori di RSA offrirono un premio di 100 dollari al primo che fosse riuscito a trovare il testo del messaggio in chiaro.

Nel 1993 un gruppo di matematici, composto da Atkins, Graff, Lenstra e Leyland, cominciarono a pensare al modo di fattorizzare il numero n in tempi umani. Per prima cosa ricalcolarono la stima fatta da Rivest nel 1977, e trovarono un errore. Probabilmente Rivest aveva contato male il numero degli zeri, perché il tempo stimato dal gruppo era di soli 4 quadrilioni di anni, e non 40, per un totale di circa 1.3·10³² moltiplicazioni modulari.

Successivamente al 1977, però, la ricerca aveva compiuto grossi passi avanti nella fattorizzazione dei numeri interi, e allo stesso tempo la velocità dei computer era aumentata enormemente. Con hardware costruito ad hoc e tecniche di pipelining, con ritardi di gate di circa 10 picosecondi, si sarebbe forse riusciti ad arrivare al record di una moltiplicazione modulare ogni nanosecondo. In questo caso, utilizzando il nuovo metodo di fattorizzazione che utilizza le curve ellittiche (scoperto da uno dei quattro matematici, Lenstra), il gruppo stimò un tempo di circa due mesi: 240 quadrilioni di volte più veloce rispetto alla stima di Rivest, per un totale di circa 5·10¹⁵ moltiplicazioni modulari. E tutto grazie al progresso nelle tecniche di fattorizzazione.

Su un computer normale, però, il tempo di calcolo era ancora proibitivo: la stima era di circa 15000 anni su una workstation Sparc 10.

Stime fatte utilizzando un altro metodo di fattorizzazione, il crivello quadratico, abbassarono ulteriormente il tempo di calcolo: circa 120 anni su una workstation Sparc 10. Per rendere i calcoli indipendenti dalla macchina, si usa un'unità di misura diversa, il mips·anno. Un mips corrisponde a un milione di operazioni elementari per secondo, e quindi un mips·anno corrisponde al numero di operazioni elementari che una macchina con potenza uguale a 1 mips può effettuare in un anno. La stima per fattorizzare n era di circa 4200 mips·anno. Ce la potevano fare.

Non da soli, naturalmente, ma con l'aiuto di uno dei più grandi gruppi di ricerca dell'epoca: il calcolo distribuito su internet.

Le stime erano le seguenti: servivano circa 8 milioni di relazioni, ognuna delle quali occupava circa 350 byte. Il programma doveva tenere in memoria un numero di fattori compreso tra 400000 e 600000, per un totale di 8 MByte. In tutto, il programma utilizzava 10.5 MByte di memoria. All'epoca molti computer affacciati a internet erano dotati di meno di 16 MByte, e molti ne avevano meno di 8.

Atkins e Leyland compilarono il loro programma per il maggior numero possibile di workstation e PC. Il gruppo ottenne in prestito un file server del MIT per la durata del progetto: era un DEC 5000/240 con 32 MByte di RAM e due dischi da 985 MByte. Il terzo disco fu aggiunto poco tempo dopo.

Il 19 agosto 1993 il progetto pubblicò la sua prima richiesta di aiuto nella number theory net, il 23 agosto scrisse ai cypherpunk e al PGP development group, e infine il 24 agosto nei newgroup alt.hackers, alt.security, alt.security.pgp, alt.security.ripem, comp.arch, comp.security.misc, sci.crypt, sci.math (questo, almeno, è quanto riporta l'articolo scritto dal gruppo, ma google groups riporta un'alta data).

Il codice venne fatto girare su macchine molto diverse tra loro: c'erano degli 80386sx a 16MHz e dei Cray C90. Non si riuscì a compilare il codice per una Thinking Machine CM-5, mentre una azienda americana riuscì a farlo girare su due fax (sì, non è sbagliato, due fax).

Per poter fare girare il codice sul maggior numero di macchine possibile, venne ridotto lo spazio di memoria necessario al programma per girare: si passò da 10.5 a 6.5Mbyte, ma il programma dimezzò la sua velocità. Nonostante questo rallentamento, il bilancio fu positivo, perché poterono partecipare molti computer che altrimenti non avrebbero avuto le caratteristiche necessarie.

Parteciparono 600 persone e 1600 computer, una piccola frazione di tutte la capacità di calcolo disponibile. Se tutta la potenza di internet fosse stata disponibile, n sarebbe stato fattorizzato in sole tre ore. L'ottanta per cento del lavoro fu svolto dai volontari, il restante venti per cento da alcuni computer MasPar gestiti da Lenstra e collaboratori.

Il 21 marzo 1994 il coordinamento del progetto aveva raccolto il numero necessario di relazioni, e il 22 marzo venne spedito a tutti i contributori il messaggio di cease and desist. Dopo 220 giorni di setacciamento, il 26 marzo fu fatto il conteggio finale: c'erano 8424486 relazioni da analizzare. Una parte di queste relazioni fu salvata su nastro magnetico e spedita da Atkins a Lenstra mediante il normale servizio postale notturno. Un'altra parte fu trasferita via ftp.

I dati vennero analizzati da un computer MasPar MP-1: dopo 45 ore, alle 18:15 UT del 2 aprile 1994, venne trovata la fattorizzazione di n:

n = 3490529510847650949147849619903898133417764638493387843990820577 ·

32769132993266709549961988190834461413177642967992942539798288533

Ecco l'annuncio.

Il messaggio cifrato da Rivest venne quindi decifrato. Il testo in chiaro era:

200805001301070903002315180419000118050019172105011309190800151919090618010705

che, tradotto secondo la codifica utilizzata da Rivest, diventa:

THE MAGIC WORDS ARE SQUEAMISH OSSIFRAGE

Vennero usati dai 4000 ai 6000 mips·anno.

(Tutta la storia è raccontata qui)

⇐ · ⇒

Alice, Bob e Eva — modpow

“Senti, ma secondo te era facile decrittare quel codice che mi hai dato da studiare?”.

“Eh, no”.

“E poi, con dei numeri così, come si fa anche solo a calcolare la potenza e il modulo? Sono numeri giganteschi”.

“Quello non è un problema, si fa in un attimo con qualunque linguaggio. Vanno benissimo anche i linguaggi ad alto livello, che supportano gli interi a qualunque precisione. Anche se sono linguaggi interpretati, non c'è problema”.

“Davvero?”.

“Sì, guarda, ti faccio vedere una funzione pyhton che fa il calcolo rapidamente”.

def modpow(c,d,n):
  m=1
  while d >= 1:
    if d & 1:
      m=c*m % n
    c=c*c % n
    d = d >> 1
  return m

“Mh, non capisco mica bene”.

“Eh, perché è stato scritto tenendo presente le proprietà della notazione binaria, ma potrebbe essere scritto anche in maniera più chiara”.

“E non potevi scriverlo in maniera più chiara subito?”.

“Certo che no, è come quando i medici scrivono le diagnosi o le ricette. Meno gente capisce, più si sentono superiori”.

“Andiamo avanti, per piacere”.

“Ok, ok. Comunque la notazione che ho usato è anche didattica, eh”.

“Eh, va bene, sentiamo la scusa”.

“Per esempio, la riga if d & 1 si domanda se d AND 1 è vera, cioè se d, scritto in binario, finisce con 1, cioè se d è congruente a 1 modulo 2. È un modo rapido per controllare se d è dispari”.

“Ah, bello”.

“E la riga che trasforma d in d>>1 sta a significare che i bit di d vengono tutti spostati di uno verso destra. In pratica è la divisione di d per 2, gettando via il resto”.

“E questa serie di operazioni è proprio la potenza c^d mod n?”.

“Sì. Funziona in questo modo: si prende l'esponente d in forma binaria e lo si esamina una cifra alla volta, a partire dal fondo. Se c'è una cifra zero, significa che l'esponente è pari. Allora faccio il quadrato di c e divido l'esponente 2. Se invece c'è una cifra uno, l'esponente è dispari. Allora, prima moltiplico m per c, e poi faccio come prima. Poi getto via l'ultima cifra binaria di d e ricomincio. Ecco le formule:”.

c^d = (c²)^d/2, se d è pari;
c^d = c(c²)^d/2, se d è dispari (e d/2 è la divisione in cui getto via il resto).

“Ah, e quindi non devo fare un'infinità di moltiplicazioni”.

“Eh, no, devi fare tante operazioni quante sono le cifre binarie di d: questo algoritmo ha quindi bisogno di un numero di operazioni proporzionale al logaritmo in base 2 di d. In questo caso il ciclo viene eseguito solo 426 volte”.

“Sembra quasi miracoloso”.

“Ora che hai capito, ti scrivo la funzione in maniera più comprensibile:”.

def modpow(c,d,n):
  m=1
  while d>=1:
    if d % 2 == 1:
      m=c*m % n
    c=c*c % n
    d = d/2 
  return m

“Ah, grazie, serve a molto adesso… Comunque, rimane il problema di fattorizzare quell'n enorme. Da quanto ho capito fino ad ora, non esiste un modo veloce per farlo”.

“Eh, no. La storia di come è stato fattorizzato n la raccontiamo la prossima volta”.

⇐ · ⇒

Alice, Bob e Eva — La radice discreta

“Un altro sistema che potrebbe avere Alice per decrittare la codifica RSA senza conoscere φ(n) è quello di calcolare la radice discreta”.

“Cosa sarebbe?”.

“Bob, per codificare m, ha usato la formula c ≡ m^e mod n. Potremmo dire che m è la radice discreta e-esima di c, in analogia a quanto si fa con i numeri reali”.

“Ah”.

“Ad oggi non è noto alcun metodo per calcolare la radice discreta in modo veloce. Come al solito, però, non si sa se in futuro questo metodo verrà trovato oppure no. Tra l'altro, questo problema potrebbe essere anche più semplice del problema della fattorizzazione”.

“Perché?”.

“Perché mediante la fattorizzazione si può calcolare la chiave privata di Alice e, quindi, decrittare ogni messaggio destinato ad Alice. Estraendo la radice discreta del messaggio, invece, si può decrittare solo quel singolo messaggio. E, forse, decrittare un unico messaggio può essere più semplice che decrittare ogni messaggio”.

“Insomma, non si sa niente e si spera che le cose vadano bene”.

“Esattamente. Un'altra cosa carina alla quale bisogna stare attenti, ma che non capita molto spesso, è quella dei messaggi che rimangono fissi”.

“Eh?”.

“Ti faccio un esempio. Ricordi quando abbiamo fatto una prova con RSA utilizzando la chiave pubblica (n,e) = (16637,11)?”.

“Sì”.

“Prova a crittare questo messaggio: m = 2793”.

“Ecco: 2793¹¹ mod 16637 = 2793. Ehi, come è possibile?”.

“Eh, succede. Nei casi reali, con numeri giganteschi, succede rarissimamente, ma bisogna stare comunque attenti. In questo caso, con numeri piccoli, succede 32 volte. Ti lascio come esercizio il calcolo”.

“Mamma mia, mi sembra che questa crittografia sia un sistema sempre meno sicuro”.

“Eh, in genere il sistema è sicuro, ma ci possono essere tanti piccoli casi particolari che lo rendono facilmente attaccabile. Ma, a volte, può essere colpa dell'utente”.

“In che senso?”.

“Supponi che due utenti utilizzino due esponenti diversi, ma lo stesso n. Avrebbero, in pratica, due chiavi di questo tipo: (n,e₁), (n,e₂). Bob invia lo stesso messaggio m ai due utenti: esso verrà crittato in due modi diversi, naturalmente”.

“Sì, si fanno due calcoli diversi: c₁ = m^e₁ mod n, c₂ = m^e₂ mod n”.

“Bene. Eva li intercetta tutti e due, e calcola preventivamente due numeri a e b in modo tale che ae₁ + be₂ = 1”.

“Ah, una equazione diofantea. Queste ho imparato a risolverle”.

“Perfetto. Allora calcola anche c₁^a c₂^b”.

“Vediamo: c₁^a c₂^b = m^ae₁ m^be₂ = m^{ae₁ + be₂} = m¹ = m. Ehi, Eva decritta il messaggio!”.

“Eh, sì. Quindi è imperativo usare n diversi. Ma con 150 cifre a disposizione, c'è abbondanza di numeri primi”.

“Ci sono altri problemi?”.

“Ce ne sono di complicati, casi particolari in cui la fattorizzazione è veloce, e cose del genere. Quelli li lascerei perdere, mentre vorrei raccontarti un'ultima situazione critica che potrebbe compromettere la sicurezza”.

“Quale?”.

“Supponi di essere in guerra, per fare un esempio. Tu devi spedire con regolarità dei messaggi in cui trasmetti le coordinate per una ricognizione, o un bombardamento, o che so io. I tuoi messaggi potrebbero essere creati automaticamente, potrebbero avere una struttura standard ed essere diversi solo nel punto in cui scrivi le coordinate”.

“Sì, giusto”.

“Allora Eva potrebbe semplicemente creare tutti i possibili messaggi che tu puoi spedire, crittarli tutti quanti con la chiave pubblica di Alice, e confrontare il suo dizionario di messaggi con il messaggio che ha appena intercettato”.

“Oh cavolo, così riuscirebbe a decrittare quello che scrive Bob senza rompere RSA”.

“Esatto. Per evitare questi problemi si usa una tecnica chiamata padding”.

“In cosa consiste?”.

“Consiste nell'inserire dei caratteri casuali qua e là all'interno del messaggio, in modo da non avere mai due messaggi che sono diversi per pochi caratteri”.

“Caratteri casuali?”.


“Sì, se io volessi spedirti il messaggio Ci vediamo domani potrei, prima di crittarlo, modificarlo in Topolino Ci Pippo vediamo Pluto domani. Noi siamo già d'accordo che i personaggi dei fumetti devono essere cancellati dal messaggio, naturalmente”.

“Ah. E se Eva intercetta questo nostro accordo?”.

“Nessun problema: anche se lei è a conoscenza di questa modifica, non sa quali siano i nomi dei personaggi che io voglio usare, e non sa dove li inserisco. Quindi il suo attacco basato sullo schema fisso dei messaggi non funziona più. Il sistema usato nella realtà si chiama Optimal Asymmetric Encryption Padding”.

“Peccato, mi sarebbe piaciuto un Comics and Cartoons Encryption Padding”.

“Eh, vabbé, non si può avere tutto. Ti lascio un esempio reale di codice crittato con RSA. Il messaggio è un testo codificato in questo modo: A = 01, B = 02, …, Z = 26, e lo spazio è uguale a 00”.

“Ok”.

“Vado a capo perché non ci sto:”.

n = 11438162575788886766923577997614661201021829672124236256256184293
    5706935245733897830597123563958705058989075147599290026879543541

e = 9007

c = 9686961375462206147714092225435588290575999112457431987469512093
    0816298225145708356931476622883989628013391990551829945157815154

⇐ · ⇒

Alice, Bob e Eva — Perché Eva non riesce a decrittare

Chiave pubblica (n,e) = (9017,251),
Messaggio cifrato c = 6543.

Eva vuole decrittare il messaggio senza conoscere la chiave privata. Per prima cosa scompone n:

n = 71·127.

Di conseguenza può calcolare φ(n) = 70·126 = 8820.

Grazie a φ(n) può dare inizio alla procedura per calcolare d, che deve essere tale per cui ed ≡ 1 mod 8820. L'equazione diofantea da risolvere è la seguente:

251d - 8820k = 1.

Si esegue la divisione con resto 8820/251:

8820 = 251·35 + 35.

Si sostituisce 8820 e si raccoglie:
251d - (251·35 + 35)k = 1,
251(d - 35k) - 35k = 1.

Indichiamo con A l'espressione tra parentesi d-35k:

251A - 35k = 1

Ora si può ripetere il procedimento. Si esegue la divisione con resto 251/35:

251 = 35·7 + 6.

Si sostituisce 251 e si raccoglie:

(35·7 + 6)A - 35k = 1,
35(7A - k) + 6A = 1.

Indichiamo con B l'espressione tra parentesi 7A - k, e ricominciamo (anche se si vede già il risultato: B = -1, A = 6).

35B + 6A = 1.

Si esegue la divisione con resto 35/6:

35 = 6·5 + 5.

Si sostituisce 35 e si raccoglie:

(6·5 + 5)B + 6A = 1,
6(5B + A) + 5B = 1.

Indichiamo con C l'espressione tra parentesi 5B + A, e ricominciamo (anche se si vede già il risultato: C = 1, B = -1).

6C + 5B = 1.

Si esegue la divisione con resto 6/5:

6 = 5·1 + 1.

Si sostituisce 6 e si raccoglie:

(5·1 + 1)C + 5B = 1,
5(C + B) + C = 1.

A questo punto C ha coefficiente 1 e tutti (compresi i calcolatori) vedono la soluzione: C + B = 0, C = 1.

Ora si eseguono le sostituzioni all'indietro:

C = 1,
C + B = 0, B = -C, B = -1,
5B + A = C, A = C - 5B, A = 1 + 5, A=6,
7A - k = B, k = 7A - B, k = 42 + 1, k = 43,
d - 35k = A, d = 35k + A, d = 35·43 + 6, d = 1511.

Finalmente è stato trovato d, ora si può decrittare il messaggio:

m ≡ c^d mod n = 6543¹⁵¹¹ mod 9017 = 102.

“Quanti calcoli!”.

“Bè, ma li fanno i calcolatori, mica si fanno a mano”.

“E non è facile per Eva, con calcolatore alla mano, decrittare il messaggio? Perché in questo esempio ci siamo riusciti, mentre nella realtà non ci si riesce?”.

“Ti rispondo con una domanda: hai notato su cosa si basa la ricerca di d?”.

“Sulla definizione di d, suppongo: d è tale per cui ed è congruente a 1 modulo φ(n)”.

“Quindi, dato che e è pubblico, riesci a calcolare il valore di d se conosci φ(n)”.

“Giusto”.

“Supponi allora che esista un metodo veloce per calcolare φ(n) a partire da n. Sapendo che n è il prodotto di due numeri primi p e q (che Eva non conosce), si possono fare i calcoli seguenti:”.

φ(n) = (p - 1)(q - 1) = pq - (p + q) + 1 = n - (p + q) + 1.

“Ok, ma a cosa mi serve?”.

“Ricordati che le incognite sono p e q. Dall'equazione che abbiamo appena scritto possiamo ricavare p + q:”.

p + q = n - φ(n) + 1.

“E quindi?”.

“Dato che già conosciamo il prodotto pq = n, ora siamo in possesso di due dati: la somma di due numeri e il loro prodotto. Un problema che sanno risolvere gli studenti di seconda superiore è proprio quello della ricerca di due numeri conoscendone la somma e il prodotto”.

“Ah, è vero, basta risolvere un'equazione di secondo grado. Se indichiamo con S la somma e con P il prodotto dei due numeri da trovare, l'equazione da risolvere è x² - Sx + P = 0”.

“Esatto. Quindi potremmo trovare facilmente p e q, cioè potremmo fattorizzare n. Riassumendo: se Eva fosse in grado di calcolare in modo veloce φ(n), allora sarebbe anche in grado di fattorizzare velocemente n. Dato che ad oggi non è noto un metodo veloce per fattorizzare, allora non è noto nemmeno un metodo veloce per trovare φ(n)”.

“Mh, una specie di dimostrazione per assurdo”.

“Sì, una specie, perché non è un teorema. Il fatto che ad oggi non sia noto un metodo per fattorizzare, o per trovare φ(n), non significa che in futuro non lo si possa trovare”.

“O che qualche organizzazione di controspionaggio non lo conosca già, ma lo tenga segreto”.

“Se è così, è un segreto molto ben custodito”.

⇐ · ⇒

Alice, Bob e Eva — RSA

Ecco i passi dell'algoritmo RSA.

Partiamo da Alice.

Sceglie due numeri primi p e q, grandi.
Calcola n = pq.
Calcola φ(n) = (p-1)(q-1).
Sceglie un numero e>2 primo rispetto a φ(n), piccolo.
Calcola d tale che ed ≡ 1 mod φ(n).
Pubblica (n,e), nasconde (p,q,d).

Bob vuole scrivere un messaggio m ad Alice (m è un numero, con l'attenzione che m<n)

Calcola c = m^e mod n.
Spedisce c.

Alice vuole leggere il messaggio crittato c. Per farlo, esegue il seguente calcolo:

c^d mod n =
(m^e)^d mod n =
m^ed mod n = [per definizione di d: ed ≡ 1 mod φ(n)]
m^1+kφ(n) mod n =
m·m^kφ(n) mod n =
m·(m^φ(n))^k mod n = [per il Teorema di Eulero: m^φ(n) ≡ 1 mod n]
m mod n =
m.


[Mnemonica per ricordarsi come funziona il tutto: e sta per encrypt, d per decrypt, c per cyphertext]


“Piano, piano, c'è troppa roba…”.

“Facciamo un esempio? Con dei numeri veri?”.

“Magari”.

“Ok, anche se non li prendiamo di 150 cifre. Usiamo numeri più piccoli, per capire il funzionamento”.

“Va benissimo”.

“Allora, Alice prima di tutto sceglie due numeri primi p e q, ne calcola il prodotto n e la funzione toziente. Ti propongo p = 127 e q = 131; fai tu i calcoli?”.

“Ok, allora: n = 127·131 = 16637; φ(n) = (p-1)(q-1) = 16380. Mi ricordo bene?”.

“Tutto bene, dato che n è il prodotto di due numeri primi, abbiamo che φ(pq) = φ(p)φ(q). E la funzione toziente di un primo p è uguale a p-1”.

“Adesso?”.

“Adesso Alice deve scegliere un numero e primo rispetto a 16380. Ti propongo e = 11”.

“Ora dici che devo calcolare d in modo tale che ed sia congruente a 1 modulo 16380. Ma non so mica come si fa”.

“Allora, per prima cosa si scrive che ed = 1 + 16380k. Questo è un altro modo per scrivere che ed è congruente a 1, giusto?”.

“Giusto, ricordo: è la divisione di ed per 16380: k è il quoziente e 1 il resto. Poi come andiamo avanti?”.

“Scriviamo l'espressione in questo modo, ricordandoci che e = 11: 11d-16380k = 1. Questa si chiama equazione diofantea: è una equazione di primo grado in due incognite, per le quali accettiamo solo valori interi”.

“Ok, ma come si risolve?”.

“Si usa l'algoritmo di Euclide per il Massimo Comun Divisore. È come se dovessimo calcolare MCD(16380,11)”.

“Ma sappiamo già che è 1”.

“Sì, è vero, ma utilizziamo i calcoli dell'algoritmo di Euclide per semplificare l'espressione. Comincia a fare la divisione tra 16380 e 11”.

“Boh, non ho ben capito, ma provo: 16380 diviso 11 mi dà quoziente 1489 e resto 1”.

“Bene, quindi 16380 = 1489·11+1, giusto?”.

“Giusto”.

“Sostituisci allora nell'equazione iniziale 16380 con 1489·11+1”.

“Mi viene 11d - (1489·11 + 1)k = 1”.

“Bene. Ora risolvi la parentesi e raccogli il fattore 11 che compare due volte”.

“Ecco: 11(d - 1489k) - k = 1”.

“Ecco fatto, questa è un'altra equazione diofantea più semplice della precedente, perché ha dei coefficienti più bassi e, soprattutto, perché uno dei due coefficienti è uguale a 1”.

“E cosa ci faccio?”.

“La risolvi: la soluzione più semplice si ha quando il coefficiente di 11 è uguale a 1, e k = 10. In questo modo ti viene 11-10 = 1”.

“Ah, credo di capire. Quindi d-1489k = 1, e k = 10”.

“Esatto. Vai avanti, sostituisci k = 10 nella prima delle due equazioni”.

“Mi viene d = 14890+1 = 14891”.

“Ecco trovato il tuo d. Se vuoi fare una verifica, ed = 11·14891 = 163801, che è congruente a 1 modulo 16380”.

“Ho capito”.

“Quindi Alice pubblica la chiave (n,e) = (16637,11), e tiene segreti p,q e d. Anzi, dato che di p e q non se ne fa più di niente, può anche cancellarli. L'importante è che tenga segreto d = 14891”.

“Perfetto. Ora Bob deve codificare il messaggio m, ma deve essere per forza un numero?”.

“Sì, ma non c'è problema, se deve spedire un testo si mette d'accordo con Alice sul tipo di codifica da usare per trasformare lettere in numeri, ed è a posto”.

“E se Eva intercetta questa conversazione?”.

“Nessun problema, Eva può ascoltare tutto. Gli unici dati che Eva non deve assolutamente conoscere sono p, q e d, ma non vengono mai trasmessi. Ti faccio presente che non è necessario tenere Eva all'oscuro del metodo crittografico usato. Questo è un principio fondamentale della crittografia: si chiama principio di Kerckhoffs”.

“Cosa dice, questo principio?”.

“Dice che un sistema crittografico deve essere sicuro indipendentemente dal fatto che il metodo usato sia pubblico. Shannon lo riformulò con le seguenti parole: The enemy knows the system”.

“Bello, meno cose si devono tener segrete, più sicuro è il sistema”.

“Esatto. Anzi, se l'algoritmo è pubblico è meglio: gli studiosi possono analizzarlo e scoprire eventuali falle. Ora prendiamo un messaggio m: ti propongo m = 12345”.

“Provo a codificarlo: dovrei calcolare c = m^e mod n = 12345¹¹ mod 16637 = 6900”.

“Bene, questo è il messaggio crittato che viagga lungo il canale di comunicazione non sicuro da Bob verso Alice”.

“Con Eva che ascolta”.

“Esattamente. Ora vediamo come fa Alice a decrittare: prova”.

“Dunque, vediamo: Alice riceve c = 6900, e deve calcolare c^d mod n = 6900¹⁴⁸⁹¹ mod 16637 = 12345. Ehi, funziona!”.

“Certo che funziona, abbiamo dimostrato tutto”.

“Ma Eva non può fare lo stesso? Come mai non riesce a decrittare?”.

“Lo vediamo la prossima volta. Esercizio per casa: prova a craccare il seguente messaggio crittato:”.

Chiave pubblica (n,e) = (9017,251),
Messaggio cifrato c = 6543.

⇐ · ⇒

Alice, Bob e Eva — Lucchetti pubblici e chiavi private

“Alice e Bob vogliono scambiarsi un messaggio m lungo un canale di comunicazione non sicuro”.

“Cosa significa non sicuro?”.

“Significa che Eva, la spia, è in ascolto e può intercettare e leggere tutto quello che Alice e Bob si dicono”.

“Ma perché questi nomi?”.

“Sono i nomi standard in uso nella crittografia, se si parla di crittografia bisogna usare quei nomi lì”.

“Capisco Alice e Bob, hanno le iniziali A e B, vabbé. Ma Eva? Perché non Carlo? O Charles, se non vogliamo nomi italiani”.

“Prima di tutto perché la spia che ascolta i discorsi degli altri è naturalmente una donna, sono le donne che sono pettegole…”.

“Ti rendi conto di quello che hai detto, vero?”.

“Si scherza, eh”.

“Vallo a dire alle lettrici che passano di qua”.

“Ma dai, Eva è il nome standard perché è quella che fa eavesdropping, cioè intercettazione, è un gioco di parole. Tieni presente poi che in inglese è Eve, che si pronuncia come l'inizio della parola eavesdropping”.

“Mh, una battutona da Vero Matematico”.

“E non hai visto tutti i nomi: c'è Charlie, nel caso di comunicazione a tre; Chuck, un terzo partecipante cattivo; Isaac, l'internet provider; Justin, il giudice; Mallory, il malvagio spione; Matilda, la mercantessa; Steve lo steganografo; Trent, la terza parte imparziale; Trudy, l'intrusa; Zoe, l'ultimo anello della catena della crittografia. Poi ce ne sono tanti altri”.

“Voi Veri Matematici siete fonte di eterno stupore”.

“E comunque, non dimentichiamo che Eva, dipinta sempre come una spia malvagia, in realtà è quella buona: è lei che ha amato Bob per prima, e Alice gliel'ha portato via”.

“Ma cosa stai dicendo?”.

“Niente, citavo una striscia di xkcd”.

“Va bene, lascio perdere subito. Allora, Eva intercetta il messaggio. Suppongo che Alice e Bob non vogliano”.

“Eh, no. Cioè, non possono impedire che lei lo intercetti. Lei, che è accorta, lo intercetta ma non lo modifica, questo è un punto fermo. Altrimenti nasce il problema della firma digitale, ma questo lo affrontiamo più avanti”.

“Ok, Eva può solo leggere, o ascoltare. Se non possono impedire che lei intercetti il messaggio, lo dovranno crittografare, vero?”.

“Esattamente. Nella crittografia classica si usa una chiave per codificare il testo del messaggio che vogliamo mantenere segreto: solo chi è in possesso della stessa chiave può decodificarlo”.

“E qui entrano in gioco i numeri primi?”.

“No, qui no. In questo caso Alice e Bob possiedono una chiave segreta che solo loro conoscono e che permette solo a loro di leggere e scrivere i messaggi. Alice usa la chiave per crittare, Bob per decrittare”.

“E dov'è il problema?”.

“Il problema è la chiave: Alice e Bob devono essersela scambiata in un qualche momento”.

“E allora?”.

“E allora, se Eva era in ascolto anche in quel momento, è un bel problema”.

“Vabbè, che problema sarà mai: si incontrano una volta, si scambiano la chiave e sono a posto”.

“Certo, infatti durante la guerra si faceva così. E per scoprire chiavi segrete si uccideva. Ma tu saresti disposto ad andare di persona dal tuo internet provider a scambiarti una password? E ogni volta che la cambi saresti disposto ad andare da lui a dirglielo? E con la posta elettronica, come facciamo? Vai alla sede di google ogni tanto? Presso quanti siti internet sei registrato? Quanti viaggi dovresti fare? Puoi sempre affidarti alle (e fidarti delle) poste, ma come la mettiamo con la velocità?”.

“Mh, credo di capire il problema”.

“Bene, la crittografia moderna risolve questo problema. L'idea è molto semplice: io non scambio una chiave, io distribuisco i lucchetti”.

“Eh?”.

“Alice vuole che Bob possa scriverle segretamente. Alice manda a Bob il suo lucchetto; Eva, se vuole, può copiarselo, non c'è problema. Bob scrive il suo messaggio, lo chiude con il lucchetto, e lo manda ad Alice. Eva lo vede, ma non può aprirlo, perché non ha la chiave. La chiave la possiede solo Alice”.

“Geniale. Ma funziona? Guardando il lucchetto, Eva non può capire come è fatta la chiave?”.

“No, il funzionamento del metodo sta tutto qui: Eva non riesce a capire come è fatta la chiave nemmeno analizzando il lucchetto”.

“E chi è che ha inventato questa roba?”.

“Eh, questa è una storia un po' complicata. Allora, nel 1976 Diffie e Helmann pubblicarono la loro idea per scambiarsi una chiave segreta su un canale insicuro. Questo sistema prende il nome di protocollo di Diffie-Helmann. L'idea però è stata suggerita dal lavoro precedente di Merkle, e nel 2002 Helmann dichiarò:”.

Da quella volta il sistema (…) è stato conosciuto con il nome di 'Diffie-Hellman key exchange'. Sebbene questo sistema fu descritto per la prima volta in una pubblicazione firmata da me e Diffie, esso è un sistema di distribuzione di chiave pubblica, un concetto sviluppato da Merkle, e quindi, se dovessimo associarvi dei nomi, dovrebbe chiamarsi 'Diffie-Hellman-Merkle key exchange'. Spero che questo piccolo intervento possa aiutare l'intento di dare il giusto riconoscimento al contributo di Merkle all'invenzione della crittografia a chiave pubblica.

“Ed è stato così?”.

“Sì, il brevetto che descrive l'algoritmo porta anche il nome di Merkle”.

“Oh, bene”.

“Ma la storia non è finita qua. In realtà nel 1973 altri ricercatori dell'agenzia governativa per la sicurezza della Gran Bretagna avevano avuto la stessa idea, ma tutto è stato tenuto segreto fino al 1997”.

“Ma dai, e questi poveracci non hanno avuto nessun riconoscimento?”.

“Eh, no”.

“Che delusione”.

“Già. Ma andiamo avanti: nel 1978 venne pubblicato un articolo che descriveva un nuovo sistema di crittografia a chiave pubblica, concettualmente simile a quello di Diffie-Helman ma che utilizza teoremi matematici differenti; più precisamente, si serve del teorema di Eulero”.

“Oh, finalmente vediamo l'applicazione di questo benedetto teorema”.

“Il metodo si chiama RSA, dalle iniziali dei tre matematici autori dell'articolo: Rivest, Shamir e Adleman. Di solito i matematici sono molto precisi e democratici, e quando devono elencare gli autori di un articolo lo fanno sempre in ordine alfabetico”.

“E come mai questa volta Adleman è in fondo, invece di essere primo?”.

“Perché i teorici erano Rivest e Shamir. Adleman era quello che faceva i test e smontava tutti i metodi, fino al momento in cui è stato trovato un metodo funzionante. Rivest e Shamir desideravano che anche lui fosse coautore dell'articolo, ma Adleman non voleva. Alla fine ha accettato, a patto che il suo nome fosse tenuto per ultimo. E così il nuovo sistema crittografico ha preso il nome di RSA, invece di ARS”.

⇐ · ⇒

Alice, Bob e Eva — L'algoritmo di Euclide

“Uh, cos'è questa figura?”.

“Quello è un rettangolo di dimensioni 1071×462. L'animazione mostra le diverse fasi dell'algoritmo di Euclide”.

“Come funziona?”.

“Per prima cosa cerchiamo di riempire con mattonelle quadrate la zona più ampia possibile. Per questo prendiamo la dimensione più grande possibile tale per cui riusciamo a fare entrare almeno una mattonella dentro al rettangolo”.

“Direi che la misura più grande sia 462×462”.

“Infatti, è così. Quante mattonelle ci stanno?”.

“Si vede, sono due”.

“Quanto spazio avanza?”.

“Mh, devo moltiplicare 462 per 2 e fare la differenza”.

“Ti dice niente questa operazione, rispetto a tutto quello che abbiamo detto finora?”.

“Ah, ma certo, è il resto della divisione di 1071 per 462”.

“Esatto: 1071 = 2×462 + 147”.

“Quindi mi rimane un rettangolo di dimensioni 462×147”.

“Esatto. Ora ripeti il procedimento con questo nuovo rettangolo”.

“Allora, devo riempirlo con piastrelle di dimensioni 147×147. Faccio la divisione?”.

“Fai”.

“Risulta che 462 = 3×147 + 21. Quindi mi servono tre piastrelle, e rimane un rettangolo di dimensioni 147×21”.

“Bene, continua”.

“Allora, faccio un'altra divisione: 147 = 7×21. Ehi, mi viene resto zero”.

“Bene, il procedimento è finito, le ultime sette piastrelle 21×21 riempiono tutto lo spazio rimanente”.

“Quindi?”.

“Quindi 21 è un numero che è contenuto un numero intero di volte sia nella base che nell'altezza del rettangolo. Detto in altri termini, 21 divide sia 1071 che 462”.

“È il Massimo Comun Divisore?”.

“Esatto: l'algoritmo di Euclide serve per trovare il MCD tra due numeri, senza doverli fattorizzare completamente. Hai capito come funziona: se a mod b = 0 allora b è il MCD tra a e b, altrimenti si guarda il resto r della divisione, si calcola b mod r, e si continua così fino a che non si trova zero. Dato che il resto della divisione è sempre minore del quoziente, sicuramente l'algoritmo ha termine”.

“Ed è un algoritmo veloce?”.

“Sì”.

“E magari anche questo serve a qualcosa?”.

“Sì, è il più antico algoritmo non banale che conosciamo, e lo usiamo tutti i giorni”.

“Sempre per la crittografia?”.

“Eh, sì”.

“Bisognerà allora che tu mi racconti come funziona, questa crittografia”.

“La prossima volta cominciamo”.

⇐ · ⇒

Alice, Bob e Eva — PRIMES is in P

“Quello che abbiamo detto sul test di primalità di Fermat non è del tutto esatto. Esistono altri test che si comportano nel modo che ti ho descritto, ma per quello specifico test c'è un problema”.

“Quale?”.

“L'esistenza dei numeri di Carmichael”.

“Cosa sono?”.

“Sono numeri composti per i quali il test di Fermat risulta sempre 1”.

“Ahia”.

“Eh, sì. Se non ci fossero loro, il test di Fermat funzionerebbe come ti ho descritto, potresti fare i conti con le probabilità e raggiungere il grado di confidenza richiesto. Ma se incappi in un numero di Carmichael, non ti accorgeresti mai che è composto”.

“Ma sono così frequenti, questi numeri?”.

“No, per fortuna no, sono pochi. Il più piccolo è 561, ce ne sono solo 8220777 compresi tra 1 e 10²⁰, circa uno ogni diecimila miliardi di numeri”.

“Ok, sono pochi, però già prima pensavo che un test probabilistico fosse poco serio, per un Vero Matematico, poi adesso mi dici che ci sono dei numeri che non vengono scoperti: non mi piace”.

“Sì, è vero, ma esistono altri test probabilistici che non hanno questi problemi e sono più sicuri ancora. Il fatto è che fino al 2002 non si conosceva nessun metodo veloce per scoprire in modo deterministico, cioè con certezza, se un numero è primo oppure no”.

“Ehi, il 2002 non è tanto tempo fa. Che è successo?”.

“Il 6 agosto 2002 tre matematici indiani, Manindra Agrawal, Neeraj Kayal e Nitin Saxena hanno pubblicato un articolo sulla rivista Annals of Mathematics dal titolo drastico: PRIMES is in P”.

“Cosa significa?”.

“Nell'intoduzione al loro lavoro, gli autori fanno una storia dei test di primalità, partendo proprio dal nostro test di Fermat e mostrando l'evoluzione dei vari algoritmi. Ti leggo una frase che rappresenta la conclusione della ricerca e risponde alla tua domanda:”.

The ultimate goal of this line of research has been, of course, to obtain an unconditional deterministic polynomial-time algorithm for primality testing. Despite the impressive progress made so far, this goal has remained elusive. In this paper, we achieve this.

“Wow. Quindi hanno trovato un algoritmo polinomiale?”.

“Sì, e il problema dei test probabilistici è stato finalmente risolto. È questo il significato del titolo PRIMES is in P: P è la classe dei problemi polinomiali”.

“Oh, bene”.

“Il problema della fattorizzazione, invece, rimane: non si riesce a fattorizzare un numero in tempi decenti, ma di questo ne avevamo già parlato. È un problema relativo a uno dei problemi del millennio”.

“Sì, ricordo”.

“In questo campo ci sono stati notevoli passi avanti, ma tutti gli algoritmi di fattorizzazione sono lenti, cioè non sono polinomiali. Ma per ora va bene così”.

“Perché?”.

“Diciamo che sarebbe bello scoprire un metodo veloce per fattorizzare un numero. Il giorno in cui dovesse esserci l'annuncio sarebbe certamente un momento storico, anche perché dovrebbero cambiare molte delle nostre abitudini?”.

“In che senso?”.

“Nel senso che tutta la crittografia moderna si basa sulla non esistenza di un metodo veloce per fattorizzare un numero. Se quel metodo viene scoperto, dobbiamo fare a meno della crittografia”.

“Bah, non sarà questa gran cosa. Chi la usa?”.

“Tu, per esempio, tutte le volte che entri in gmail per leggere la tua posta”.

“Eh?”.

“Sì, sì, tutte le volte che entri in un sito sicuro, che fai acquisti su internet, che inserisci qualche password (a meno che tu non faccia girare le password in chiaro, ma non ti conviene molto)”.

⇐ · ⇒

Alice, Bob e Eva — Test di primalità

Fattorizzare n è lento, stabilire se n è primo è veloce.

“Un aforisma?”.

“No, è quello che abbiamo sperimentato la volta scorsa. Ci si mette poco tempo per stabilire se un numero è primo oppure no, in tre minuti abbiamo analizzato un numero di 317 cifre. Invece per fattorizzare un numero ci si mette molto tempo, più di un minuto per sole 82 cifre, se ricordi”.

“Ricordo, ricordo. Ma come mai questa differenza?”.

“Eh, finora non è stato scoperto alcun algoritmo veloce per fattorizzare. Cioè, ne conosciamo di molto più veloci rispetto alla tecnica divisioni successive per tutti i numeri primi fino alla radice quadrata del numero, ma sono ugualmente lenti”.

“Si può quantificare in qualche modo, questa velocità?”.

“Sì, si dice che i test di primalità sono polinomiali”.

“Cosa significa?”.

“Che il tempo necessario per completare l'esecuzione del programma è proporzionale a una qualche potenza del numero di cifre di cui è composto il numero da fattorizzare”.

“Qualunque potenza va bene?”.

“Bé, più piccola è la potenza, più veloce è il programma. Il fatto è che gli algoritmi per fattorizzare non sono polinomiali, ma esponenziali, o quasi esponenziali (non chiedermi la definizione di quasi esponenziale perché non c'è accordo nemmeno tra gli informatici, comunque sono molti più lenti rispetto agli altri)”.

“Ok, ma perché?”.

“Questo è uno dei problemi aperti della matematica, uno dei cosiddetti problemi del millennio”.

“Quelli da un milione di dollari?”.

“Precisamente. In questo caso la questione è la seguente: esistono problemi per i quali è molto facile verificare una soluzione, se la si possiede, ma che sono praticamente impossibili da risolvere direttamente? Sembra proprio che il problema della fattorizzazione di un numero appartenga a questa categoria: è molto facile moltiplicare due fattori, ma è molto difficile scomporre un numero”.

“Sembra?”.

“Sì, stiamo parlando di un problema aperto, detto P vs NP. Tra l'altro, se si riesce a trovare un algoritmo polinomiale (quindi veloce) che risolve uno solo dei problemi della categoria NP (quella dei problemi difficili da risolvere), allora è stato dimostrato che tutti i problemi di quella categoria possono essere risolti in tempo polinomiale. E la sicurezza della crittografia moderna non esisterebbe più”.

“Ma finora non è stato trovato, vero?”.

“No, no, il milione di dollari è ancora lì, e noi continuiamo a fattorizzare i numeri in modo lento. Se vogliamo dirla tutta, è possibile che la dimostrazione della congettura P vs NP sia stata trovata da qualche matematico, il quale magari è stato pagato a peso d'oro dalla NSA per non rivelare l'informazione a nessuno. Ma questo è complottismo, e comunque noi poveri mortali non lo sapremo mai…”.

“Ma dai, figuriamoci”.

“Guarda che è già successo: alcune tecniche di crittanalisi sono state secretate dalla NSA e rese pubbliche solo in tempi recenti, dopo che sono state riscoperte da altri studiosi”.

“Wow, sembra roba da spie!”.

“Già. La seconda guerra mondiale è stata vinta anche grazie ai crittanalisti, per dire”.

“Che roba”.

“Vogliamo tornare al nostro metodo veloce per vedere se un numero è primo?”.

“Ok. Come si fa?”.

“Ti ricordi il teorema di Fermat?”.

“Sì, diceva che se un numero p è primo, allora a^p-1 ≡ 1 mod p”.

“Bene, ribaltalo”.

“Eh?”.

“Come dicono i logici, trova la proposizione contronominale”.

“Ah, se pensi che adesso sia più chiaro…”.

“Insomma, fai come si fa nelle dimostrazioni per assurdo. Cosa puoi dire se succede che a^p-1 è diverso da 1 modulo p?”.

“Ah, posso dire che certamente p non è primo, perché se lo fosse allora a^p-1 dovrebbe essere congruente a 1”.

“Molto bene. Questo è già un test di non primalità”.

“Aspetta, aspetta, non ho mica capito. Il numero di cui devo testare la primalità qual è? È a oppure p?”.

“Il numero è p. Ti faccio un esempio, supponiamo che tu debba analizzare il numero 341, vuoi sapere se è primo”.

“Va bene”.

“Questo è p. Ora scegli a = 2, per esempio. Ho scelto un numero qualunque, più piccolo è meglio è. Naturalmente devo prenderlo primo rispetto a p, come dice il teorema di Fermat”.

“Va bene, 2 non divide 341. Adesso?”.

“Adesso calcolo 2³⁴⁰ mod 341”.

“E come faccio?”.

“Non è un problema, nemmeno di memoria: puoi fare un programmino che calcola la potenza per moltiplicazioni successive, e dopo ogni moltiplicazione calcoli il modulo: in questo modo il numero non diventa mai troppo grande. Comunque molte calcolatrici lo fanno, anche quella di windows”.

“Ah, ok. Provo: risulta 1”.

“Peccato”.

“Come peccato?”.

“Se risulta 1 significa che non possiamo dire niente, solo se non risulta 1 allora possiamo concludere che il numero non è primo”.

“E allora come facciamo?”.

“Prova con un altro valore di a, per esempio a = 3. Quanto fa 3³⁴⁰ mod 341?”.

“Dice che fa 56”.

“Perfetto. Quindi 341 non è primo”.

“Fantastico, l'abbiamo trovato senza calcolare i fattori di 341. Ho capito”.

“Purtroppo questo non è proprio un test di primalità, anzi; come ti dicevo è un test di non primalità”.

“Eh, non va mica bene. Il programma su internet riesce invece a scoprire se un numero è primo, non solo se è composto”.

“Infatti.”.

“Ma allora come funziona?”.

“Ora ti dirò qualche inesattezza, ma solo per capire l'idea di base. Poi mi correggerò e ti dirò come stanno le cose con precisione”.

“Va bene”.

“Allora, abbiamo detto che se il test di Fermat restituisce 1, non possiamo dire niente del numero: insomma, potrebbe essere sia primo che composto”.

“Giusto”.

“Allora, se un numero non è primo, risulta che nel cinquanta per cento dei casi il test fornisce una risposta uguale a 1, nell'altro cinquanta per cento dei casi invece il test fornisce una risposta diversa da 1, e quindi ci assicura la non primalità. Questa è una inesattezza, ma prendila per buona adesso”.

“Va bene”.

“Quindi se il primo tentativo su un numero ti dà un 1, ciò significa che il numero non è primo con probabilità uguale a 1/2”.

“Giusto, e quindi io non so niente”.

“Certo. Supponi di ripetere il test con un'altra base, e di nuovo trovi 1. Ora la probabilità che il numero non sia primo diventa 1/4, al terzo tentativo diventa 1/8, e così via”.

“Bè, però non ho la certezza”.

“No, certo, ma ti bastano 10 passi per arrivare a una probabilità che il numero sia primo del 99.9%. E 10 passi sono pochi, fanne qualcuno in più e la probabilità di sbagliare diventa più bassa della probabilità che ti cada un meteorite sulla testa, o che il tuo computer abbia sbagliato i calcoli, o che un ladro indovini la tua password tirando a caso, al primo colpo”.

“Ok, va bene, ai fini pratici magari può anche andar bene, ma non mi dire che un Vero Matematico si accontenta così”.

“Ah, no, certo che no. Anche perché quello che ti ho detto non è del tutto vero”.

⇐ · ⇒

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”.

⇐ · ⇒

Alice, Bob e Eva — La funzione toziente

“Abbiamo detto che si chiama funzione toziente, e si indica con φ(n), il numero di interi positivi minori o uguali a n e primi rispetto a n”.

“Sì, c'è una formula per calcolarla?”.

“Eh, magari. No, fino ad oggi non è stata trovata nessuna formula diretta”.

“E quindi come si fa? Per tentativi?”.

“Si può procedere per tentativi, sì, soprattutto se n è piccolo. Però conosciamo un po' di proprietà che possono aiutarci. Per esempio, se p è primo allora φ(p) = p-1”.

“Va bene, questa è facile, se p è primo tutti gli interi minori di p sono primi rispetto a p”.

“Quindi, tanto per fare un esempio, φ(5) = 4. Cosa puoi dirmi di φ(25)?”.

“Non è un numero primo, non so, dovrei fare i conti”.

“Però è una potenza di un numero primo, puoi ragionare un po' su questo fatto”.

“Vediamo: 25 contiene solo il fattore 5, quindi ogni numero primo rispetto ad esso non dovrà contenere il fattore 5”.

“Quanti sono i numeri minori o uguali di 25 che contengono il fattore 5?”.

“Tutti i multipli di 5”.

“E quanti sono?”.

“Bè, 5. Sono 5, 10, 15, 20, 25”.

“Tutti gli altri numeri sono primi con 25, quindi”.

“Sì, giusto. Quindi ci sono 25 numeri minori o uguali a 25, 5 dei quali non sono primi rispetto a 5. Quindi ne rimangono 20: φ(25) = 20”.

“E se ti chiedo di calcolare φ(5³)?”.

“Dovrei ragionare come prima, tra tutti i 125 numeri che posso prendere in considerazione ce n'è uno ogni 5 che è multiplo di 5”.

“E che devi togliere”.

“Sì, esatto, quindi φ(5³) = 5³-5²”.

“In generale, se p è primo allora φ(p^k) = p^k-p^k-1. Questa è una prima regolina”.

“Ce ne sono altre?”.

“Sì, ce n'è una che è molto comoda per i calcoli. Dice questo: se n e m sono due interi primi tra loro, allora φ(nm) = φ(n)φ(m). Però è un po' brigosa da dimostrare, se permetti ti faccio vedere solo qualche esempio”.

“Ok, va bene”.

“Per esempio, vuoi calcolare φ(360). Non è un numero primo, quindi puoi scomporlo, e risulta che 360 = 2³3²5”.

“Ok, sono tre fattori primi tra loro, quindi posso scrivere φ(360) = φ(2³)φ(3²)φ(5)”.

“Ora, per quanto riguarda φ(2³), puoi applicare la seconda formula che abbiamo scritto”.

“Giusto: φ(2³) = 2³-2² = 4”.

“Per φ(3²) puoi procedere allo stesso modo”.

“Sì, è vero: φ(3²) = 3²-3 = 6”.

“E infine φ(5)”.

“Che è uguale a 4”.

“Quindi φ(360) = 4·6·4 = 96”.

“Bene, se sappiamo scomporre in fattori sappiamo anche calcolare φ, a questo punto”.

“Esatto. Il problema è proprio lì”.

⇐ · ⇒

Alice, Bob e Eva — Un teorema un po' più grande

“Il teorema di Fermat può essere usato per risolvere calcoli di questo tipo: 31⁴¹⁶ mod 11”.

“In che modo?”.

“Dato che 11 è un numero primo, e che 31 non è multiplo di 11, il teorema afferma che 31¹⁰ ≡ 1 mod 11”.

“Credo di capire: posso scrivere 31⁴¹⁶ come 31⁴⁰⁰ moltiplicato per 31¹⁶. Ora so che 31⁴⁰⁰ ≡ 1, quindi mi rimane da calcolare 31¹⁶”.

“Che è un numero più gestibile”.

“Bé, mica tanto”.

“Sì, non è facile da calcolare direttamente senza calcolatrice, ma puoi arrangiarti un po'”.

“In che modo?”.

“Comincia con il calcolo di 31 mod 11”.

“Questo è facile, viene 9”.

“Ok, ora sai che per calcolare 31² ti basta calcolare 9²”.

“Ah, giusto. Il risultato è 81, congruente a 4 modulo 11”.

“Bene, e siamo a 31². Ora puoi passare direttamente a 31⁴”.

“Calcolando 4², ottimo! Viene 16, congruente a 5”.

“Vai avanti”.

“Elevando ancora al quadrato trovo 31⁸, congruente a 25, cioè 3. Elevando ancora una volta trovo il risultato: 9”.

“Senza calcolatrice”.

“Bello, non credevo si potessero fare calcoli di questo tipo. Peccato si possano fare solo se p è primo, però. Non c'è modo di generalizzare?”.

“In effetti il modo c'è. Ricordi la dimostrazione del teorema di Fermat?”.

“Sì, bisognava moltiplicare a per tutti i numeri da 1 a p-1, poi c'era quella semplificazione a cui bisognava fare attenzione”.

“Esatto, il problema è proprio lì. Il teorema funziona perché si arriva a scrivere la formula seguente:”.

a^p-1(p-1)! ≡ (p-1)! mod p.

“Mi ricordo, sì”.

“E poi si fanno delle considerazioni che ci permettono di semplificare la quantità (p-1)!”.

“E non possiamo farle anche se p non è primo?”.

“No, se p non è primo allora è composto da fattori più piccoli di p, che potrebbero essere fattori della prima parte dell'espressione, o della seconda. Insomma, non lo sappiamo. Dobbiamo cambiare un po' le carte in tavola”.

“Come?”.

“Per prima cosa non possiamo più moltiplicare a per tutti i numeri da 1 a p-1, perché qualcuno di questi fattori potrebbe essere un fattore di p. Dobbiamo selezionare i moltiplicatori, prendendo solo i numeri minori o uguali a p e primi rispetto a p”.

“Ah, bene, in questo modo siamo sicuri che non ci siano fattori comuni. Però così mi perdo un po', possiamo fare come l'altra volta? Io faccio degli esempi numerici, e tu generalizzi?”.

“Va bene, prendi per esempio a = 2 e p = 15”.

“Ok. Allora, non devo moltiplicare a per tutti i numeri da 1 a 14, ma solo per i numeri che sono primi rispetto a 15. Dovrebbero essere questi:”.

1, 2, 4, 7, 8, 11, 13, 14.

“Giusto, sono loro. Li chiamiamo a_i, con i che varia da 1 fino a k. Con k ho indicato il numero di fattori primi rispetto a p, che nel tuo esempio sono 8”.

“Va bene. Faccio la moltiplicazione per a, allora. Dovrei ottenere questi altri numeri:”.

2, 4, 8, 14, 16, 22, 26, 28.

“Perfetto. Io li indicherò in questo modo:”.

a·a₁, a·a₂, …, a·a_k.

“Fin qua ci sono”.

“Andiamo avanti: ognuno di questi numeri sarà congruente, modulo p, a uno dei valori a_i”.

“Proprio a uno di quelli? Non può accadere che risulti uno dei valori non primi con p?”.

“Ottima domanda: non può accadere, e adesso lo dimostriamo. Supponi che esista un certo elemento a_i tale per cui il prodotto a·a_i sia congruente a un numero n che non è primo con p”.

“Sì, ti seguo, stai facendo una dimostrazione per assurdo”.

“Esatto. Se fosse così, vorrebbe dire che a·a_i = ph + n, e in questo caso potrei raccogliere da p e da n il fattore comune, che dovrebbe essere un fattore anche di a·a_i. Questo vorrebbe dire che p e a·a_i hanno un fattore comune”.

“E questo è impossibile, ho capito: avevamo scelto a e tutti gli a_i in modo tale che non avessero fattori comuni con p”.

“Inoltre, è anche impossibile che due diversi prodotti, diciamo che siano a·a_i e a·a_j (con i diverso da j) siano congruenti”.

“Anche questo si dimostra per assurdo?”.

“Sì. Se fossero congruenti, la loro differenza dovrebbe essere un multiplo di p”.

“Differenza che possiamo scrivere così, se non sbaglio: a(a_i-a_j)”.

“Sì. Se quella espressione fosse multiplo di p, vorrebbe dire o che a è multiplo di p…”.

“Impossibile, per ipotesi”.

“…o che (a_i-a_j) è multiplo di p. In altri termini, a_i dovrebbe essere congruente a a_j”.

“Impossibile anche questo, gli a_i sono tutti diversi”.

“Esatto”.

“Aspetta che faccio una prova: calcolo la congruenza modulo 15 di tutti i numeri che ho elencato prima. Mantenendo l'ordine, ottengo:”.

2, 4, 8, 14, 1, 7, 11, 13.

“Come vedi, sono tutti i tuoi a_i riordinati”.

“Ok, ci sono. Come andiamo avanti?”.

“Procediamo come nella dimostrazione del teorema di Fermat: moltiplichiamo tra loro tutti quei fattori”.

“Bene, proviamo. Dovrebbe risultare così:”.

(a·a₁)(a·a₂)·…·(a·a_k).

“Che puoi scrivere, in forma un po' più abbreviata, così:”.

a^ka₁a₂…a_k.

“E questa espressione, grazie alla dimostrazione che hai appena fatto, è congruente al prodotto di tutti gli a_i”.

“Proprio così. L'espressione finale è questa:”.

a^ka₁a₂…a_k ≡ a₁a₂…a_k mod p.

“Ora, se si potesse semplificare a destra e a sinistra…”.

“Ma si può, grazie alle ipotesi che abbiamo fatto, proprio come avevamo fatto nella dimostrazione del teorema di Fermat. Quella congruenza significa che a₁a₂…a_k(a^k-1) è multiplo di p. Dato che tutti gli a_i sono primi con p, possiamo concludere che è l'espressione a^k-1 ad essere multipla di p. E cioè, concludendo:”.

a^k ≡ 1 mod p.

“Ecco la congruenza uguale a 1 che tanto mi piace. Ha un nome, questo teorema?”.

“Sì: si chiama teorema di Eulero, anche se non è un nome molto felice”.

“Perché?”.

“Perché Eulero ne ha fatti a montagne, di teoremi. Qualcuno lo chiama anche teorema di Eulero-Fermat, giusto per connotarlo un po' di più, dato che è una generalizzazione del teorema di Fermat. Te lo enuncio per bene:”.

Dato p intero maggiore di 1, esiste un intero positivo φ(p) tale che, per ogni a primo con p, accade che

a^φ(p) ≡ 1 mod p.

“Addirittura una lettera greca?”.

“Sì. Se ricordi, nella dimostrazione abbiamo indicato con k il numero di interi positivi minori di p e primi rispetto a p. Questo numero è naturalmente funzione di p”.

“Certo, al variare di p cambia il numero di numeri minori di p e primi rispetto ad esso”.

“Bene: questo numero viene indicato con il simbolo φ(p), e la funzione φ viene detta funzione toziente”.

“Che razza di nome”.

“Già. Ho fatto un po' di ricerche: Eulero non ha mai usato quel termine. È stato inventato da J.J. Sylvester, un matematico inglese al quale piaceva inventare parole nuove”.

⇐ · ⇒

Alice, Bob e Eva — Un piccolo teorema

“La domanda era: è sempre possibile trovare una potenza che, in modulo, risulti uguale a 1?”.

“E la risposta è?”.

“Dipende”.

“Ah, gran risposta. Da cosa dipende?”.

“Te lo spiego con un esempio. Prima vediamo un caso particolare, poi vediamo cosa dice il teorema”.

“Va bene”.

“Prendiamo due numeri: uno lo chiamiamo a, e diciamo che è uguale a 4, l'altro lo chiamiamo p e diciamo che è uguale a 7”.

“Ok, a = 4, p = 7. Poi?”.

“Poi consideriamo tutti i prodotti del tipo a·1, a·2, a·3, …, a·(p-1)”.

“Cioè prendo a e lo moltiplico per tutti i numeri da 1 a p-1. Nel nostro esempio prendo 4 e lo moltiplico per tutti i numeri da 1 a 6”.

“Fai pure i conti, scrivili”.

“Ok, eccoli qua:”.

4·1
4·2
4·3
4·4
4·5
4·6

“Prima domanda: questi 6 numeri possono avere lo stesso resto quando li dividi per p (cioè per 7)?”.

“Dovrei fare i calcoli, vediamo un po':”.

4·1 ≡ 4
4·2 ≡ 8 ≡ 1
4·3 ≡ 12 ≡ 5
4·4 ≡ 16 ≡ 2
4·5 ≡ 20 ≡ 6
4·6 ≡ 24 ≡ 3

“Bene, cosa deduci?”.

“Deduco che i numeri non hanno lo stesso resto. Vedo anche che non risulta mai 0. Ah, certo, non può risultare 0 perché 4 (cioè a) non è divisibile per 7 (cioè p), e perché tutti i fattori per cui ho moltiplicato 4 sono minori di 7”.

“Molto bene. Ora proviamo a generalizzare, e consideriamo la seguente lista di prodotti:”.

a·1
a·2
a·3
…
a·(p-1)

“Uh, ora mi pare più difficile”.

“Proseguiamo come prima. La domanda è sempre la stessa: è possibile che due qualsiasi di questi numeri diano lo stesso resto quando vengono divisi per p?”.

“Come faccio a saperlo? Qua non ho effettivamente i numeri, non posso provare”.

“Ricorda la prima regola che abbiamo visto: se due numeri sono congruenti modulo p, allora la loro differenza è un multiplo di p”.

“Giusto! Allora la tua domanda potrebbe essere trasformata in questa: la differenza tra due di questi numeri è un multiplo di p oppure no?”.

“Perfetto. Calcola la differenza tra due di quei numeri scelti a caso”.

“Diciamo che uno dei due è a·h e l'altro a·k?”.

“Sì, va benissimo”.

“La differenza risulta a(h-k)”.

“Bene. È un multiplo di p?”.

“Certamente p non può dividere (h-k)”.

“Perché?”.

“Perché sia h che k sono minori di p: anche se non so quanto vale la differenza, questa è certamente minore di p”.

“Molto bene. Per quanto riguarda a, invece?”.

“Mi pare che non si possa dire niente: p potrebbe dividere a”.

“Giusto. Siccome abbiamo bisogno del fatto che i resti di quella sequenza di numeri siano tutti diversi, dobbiamo aggiungere una ipotesi. Da ora in poi dobbiamo presumere che a sia un intero non multiplo di p”.

“Se è così, allora è vero che due qualsiasi di quei numeri non danno lo stesso resto quando vengono divisi per p”.

“Osserva che non possono nemmeno dare 0, come resto”.

“Certo, con le ipotesi che abbiamo non è possibile: p non divide a, e non divide nemmeno nessun numero da 1 fino a (p-1)”.

“Quindi, se i resti sono tutti diversi, sono p-1, e 0 è escluso, significa che otterremo tutti i possibili resti, nessuno escluso”.

“Vero. In effetti, nell'esempio numerico che hai fatto compaiono proprio tutti i resti da 1 fino a 6”.

“Ok, questo è il primo punto. Ora moltiplichiamo tra loro tutti i numeri della sequenza”.

“Così?”.

(4·1)(4·2)(4·3)(4·4)(4·5)(4·6)

“Sì. In generale avremo questa espressione:”.

(a·1)(a·2)(a·3)…(a·(p-1))

“Bene. Io continuo i conti sull'esempio, e tu generalizzi?”.

“Sì, facciamo così. Come puoi scrivere l'espressione in modo più compatto?”.

“Vedo che il 4 compare in tutte le parentesi, e quindi posso scriverlo come potenza. Poi compaiono i numeri da 1 a 6, potrei usare il fattoriale. Vediamo, va bene così?”.

4⁶·6!

“Perfetto. Te le generalizzo in questo modo:”.

a^p-1·(p-1)!

“Va bene, ci sono. Adesso?”.

“Adesso ci chiediamo a cosa è congruente quella espressione, modulo p. Non fare troppi calcoli, però: usa tutte le proprietà che abbiamo visto finora. Ricordati che puoi moltiplicare e fare potenze come ti pare”.

“Allora, vediamo. All'inizio ho calcolato tutte le congruenze, so che il primo prodotto è congruente a 4, il secondo a 1, il terzo a 5, poi ho 2, 6 e infine 3. Posso moltiplicarli tutti e ottengo il risultato. Ehi!”.

“Cosa?”.

“Non è importante l'ordine con cui prendo quei numeri. Abbiamo detto prima che otteniamo tutti i resti, nessuno escluso, a parte 0. Quindi il numero che ottengo è 6 fattoriale”.

“Proprio così. Il primo punto di questa dimostrazione è servito proprio per dire che, quando calcolo a·1, a·2, …, a·(p-1) e ne faccio le congruenze modulo p, ottengo tutti i possibili resti. Quindi il prodotto di tutti quei numeri è uguale a (p-1)!. Ti scrivo la formula completa:”.

a^p-1(p-1)! ≡ (p-1)! mod p

“Bello, adesso semplifichiamo a destra e sinistra e…”.

“Piano, piano”.

“Cosa c'è?”.

“Non abbiamo mai detto che si può semplificare così. Non era una delle proprietà che abbiamo considerato”.

“Uh, già. Allora come facciamo? Lasciamo così?”.

“No, utilizziamo le proprietà note. Ricordi che abbiamo detto che se due numeri sono congruenti modulo p, allora la loro differenza è un multiplo di p?”.

“Sì, certo. È stata la prima proprietà che abbiamo visto. Se la applichiamo a quella congruenza, risulta che”.

a^p-1(p-1)! - (p-1)! è multiplo di p.

“Molto bene. Raccogliendo il fattore comune, possiamo scrivere che:”.

(p-1)!(a^p-1-1) è multiplo di p.

“Sì, vero. Mi pare però che (p-1)! non sia multiplo di p. È impossibile, contiene solo fattori minori di p”.

“Qui bisogna fare attenzione. Se p fosse composto da più fattori, qualche suo fattore potrebbe dividere (p-1)!, e qualche altro fattore potrebbe dividere (a^p-1-1), e non potremmo dire niente. Quindi abbiamo bisogno di un'altra ipotesi: p deve essere un numero primo. Se è così, il tuo ragionamento è corretto. Cosa puoi dedurre, quindi?”.

“Che sarà a^p-1-1 ad essere multiplo di p”.

“Bene. Quindi possiamo dire che a^p-1 ≡ 1 mod p”.

“Ehi, è come se avessimo fatto la semplificazione che dicevo io!”.

“Sì, ma in questo modo abbiamo dimostrato che si può fare. Non sempre si può, qui ci siamo basati sul fatto che (p-1)! non può essere multiplo di p: se al suo posto avessimo avuto un numero multiplo di p, o se p non fosse primo, non avremmo potuto concludere niente. Ti faccio un esempio: 2·5 e 2·2 sono congruenti modulo 6, ma non puoi semplificare e concludere che 2 è congruente a 5 modulo 6”.

“Ok, ho capito. Tornando al teorema, alla fine cosa abbiamo trovato?”.

“Abbiamo risposto alla domanda iniziale: è possibile trovare una potenza che risulti uguale a 1? E la risposta è: se p è un numero primo e a è un intero non multiplo di p, allora a^p-1 ≡ 1 mod p”.

“Bello”.

“E questo si chiama piccolo teorema di Fermat”.

“Ce n'è anche uno grande?”.

“Sì, ma questa è un'altra storia”.

⇐ · ⇒