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 = me mod n.
Spedisce c.
Alice vuole leggere il messaggio crittato c. Per farlo, esegue il seguente calcolo:
cd mod n =
(me)d mod n =
med mod n = [per definizione di d: ed ≡ 1 mod φ(n)]
m1+kφ(n) mod n =
m·mkφ(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 = me mod n = 1234511 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 cd mod n = 690014891 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.
venerdì 30 aprile 2010
giovedì 29 aprile 2010
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ò:”.
“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”.
“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”.
mercoledì 28 aprile 2010
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”.
martedì 27 aprile 2010
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 1020, 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:”.
“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)”.
“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 1020, 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)”.
lunedì 26 aprile 2010
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 ap-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 ap-1 è diverso da 1 modulo p?”.
“Ah, posso dire che certamente p non è primo, perché se lo fosse allora ap-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 2340 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 3340 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”.
“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 ap-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 ap-1 è diverso da 1 modulo p?”.
“Ah, posso dire che certamente p non è primo, perché se lo fosse allora ap-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 2340 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 3340 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”.
venerdì 23 aprile 2010
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·142”.
“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ì:”.
p1, p2, …, pn.
“Bene”.
“Ora considera questo numero: p1p2…pn+1. Non sta nella lista, quindi non è primo”.
“Giusto”.
“Per quale pi è divisibile?”.
“Ah, non lo so”.
“Prova a pensare: è divisibile per p1? Qual è il resto della divisione per p1?”.
“Ah, facile, resta 1, l'hai aggiunto tu”.
“Quindi quel numero non è divisibile per p1. Forse per p2?”.
“Ah, no, né per p2 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 1050+151 è primo oppure no”.
“Uh, questo è grosso. La radice è dell'ordine di 1025”.
“Ad oggi il processore più veloce fa circa 1011 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 1014 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:”.
“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:”.
“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:”.
“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 (10317-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”.
“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·142”.
“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ì:”.
p1, p2, …, pn.
“Bene”.
“Ora considera questo numero: p1p2…pn+1. Non sta nella lista, quindi non è primo”.
“Giusto”.
“Per quale pi è divisibile?”.
“Ah, non lo so”.
“Prova a pensare: è divisibile per p1? Qual è il resto della divisione per p1?”.
“Ah, facile, resta 1, l'hai aggiunto tu”.
“Quindi quel numero non è divisibile per p1. Forse per p2?”.
“Ah, no, né per p2 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 1050+151 è primo oppure no”.
“Uh, questo è grosso. La radice è dell'ordine di 1025”.
“Ad oggi il processore più veloce fa circa 1011 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 1014 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 (10317-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”.
giovedì 22 aprile 2010
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 φ(53)?”.
“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 φ(53) = 53-52”.
“In generale, se p è primo allora φ(pk) = pk-pk-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 = 23325”.
“Ok, sono tre fattori primi tra loro, quindi posso scrivere φ(360) = φ(23)φ(32)φ(5)”.
“Ora, per quanto riguarda φ(23), puoi applicare la seconda formula che abbiamo scritto”.
“Giusto: φ(23) = 23-22 = 4”.
“Per φ(32) puoi procedere allo stesso modo”.
“Sì, è vero: φ(32) = 32-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ì”.
“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 φ(53)?”.
“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 φ(53) = 53-52”.
“In generale, se p è primo allora φ(pk) = pk-pk-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 = 23325”.
“Ok, sono tre fattori primi tra loro, quindi posso scrivere φ(360) = φ(23)φ(32)φ(5)”.
“Ora, per quanto riguarda φ(23), puoi applicare la seconda formula che abbiamo scritto”.
“Giusto: φ(23) = 23-22 = 4”.
“Per φ(32) puoi procedere allo stesso modo”.
“Sì, è vero: φ(32) = 32-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ì”.
mercoledì 21 aprile 2010
Alice, Bob e Eva — Un teorema un po' più grande
“Il teorema di Fermat può essere usato per risolvere calcoli di questo tipo: 31416 mod 11”.
“In che modo?”.
“Dato che 11 è un numero primo, e che 31 non è multiplo di 11, il teorema afferma che 3110 ≡ 1 mod 11”.
“Credo di capire: posso scrivere 31416 come 31400 moltiplicato per 3116. Ora so che 31400 ≡ 1, quindi mi rimane da calcolare 3116”.
“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 312 ti basta calcolare 92”.
“Ah, giusto. Il risultato è 81, congruente a 4 modulo 11”.
“Bene, e siamo a 312. Ora puoi passare direttamente a 314”.
“Calcolando 42, ottimo! Viene 16, congruente a 5”.
“Vai avanti”.
“Elevando ancora al quadrato trovo 318, 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:”.
ap-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 ai, 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·a1, a·a2, …, a·ak.
“Fin qua ci sono”.
“Andiamo avanti: ognuno di questi numeri sarà congruente, modulo p, a uno dei valori ai”.
“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 ai tale per cui il prodotto a·ai 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·ai = ph + n, e in questo caso potrei raccogliere da p e da n il fattore comune, che dovrebbe essere un fattore anche di a·ai. Questo vorrebbe dire che p e a·ai hanno un fattore comune”.
“E questo è impossibile, ho capito: avevamo scelto a e tutti gli ai in modo tale che non avessero fattori comuni con p”.
“Inoltre, è anche impossibile che due diversi prodotti, diciamo che siano a·ai e a·aj (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(ai-aj)”.
“Sì. Se quella espressione fosse multiplo di p, vorrebbe dire o che a è multiplo di p…”.
“Impossibile, per ipotesi”.
“…o che (ai-aj) è multiplo di p. In altri termini, ai dovrebbe essere congruente a aj”.
“Impossibile anche questo, gli ai 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 ai 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·a1)(a·a2)·…·(a·ak).
“Che puoi scrivere, in forma un po' più abbreviata, così:”.
aka1a2…ak.
“E questa espressione, grazie alla dimostrazione che hai appena fatto, è congruente al prodotto di tutti gli ai”.
“Proprio così. L'espressione finale è questa:”.
aka1a2…ak ≡ a1a2…ak 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 a1a2…ak(ak-1) è multiplo di p. Dato che tutti gli ai sono primi con p, possiamo concludere che è l'espressione ak-1 ad essere multipla di p. E cioè, concludendo:”.
ak ≡ 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”.
“In che modo?”.
“Dato che 11 è un numero primo, e che 31 non è multiplo di 11, il teorema afferma che 3110 ≡ 1 mod 11”.
“Credo di capire: posso scrivere 31416 come 31400 moltiplicato per 3116. Ora so che 31400 ≡ 1, quindi mi rimane da calcolare 3116”.
“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 312 ti basta calcolare 92”.
“Ah, giusto. Il risultato è 81, congruente a 4 modulo 11”.
“Bene, e siamo a 312. Ora puoi passare direttamente a 314”.
“Calcolando 42, ottimo! Viene 16, congruente a 5”.
“Vai avanti”.
“Elevando ancora al quadrato trovo 318, 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:”.
ap-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 ai, 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·a1, a·a2, …, a·ak.
“Fin qua ci sono”.
“Andiamo avanti: ognuno di questi numeri sarà congruente, modulo p, a uno dei valori ai”.
“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 ai tale per cui il prodotto a·ai 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·ai = ph + n, e in questo caso potrei raccogliere da p e da n il fattore comune, che dovrebbe essere un fattore anche di a·ai. Questo vorrebbe dire che p e a·ai hanno un fattore comune”.
“E questo è impossibile, ho capito: avevamo scelto a e tutti gli ai in modo tale che non avessero fattori comuni con p”.
“Inoltre, è anche impossibile che due diversi prodotti, diciamo che siano a·ai e a·aj (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(ai-aj)”.
“Sì. Se quella espressione fosse multiplo di p, vorrebbe dire o che a è multiplo di p…”.
“Impossibile, per ipotesi”.
“…o che (ai-aj) è multiplo di p. In altri termini, ai dovrebbe essere congruente a aj”.
“Impossibile anche questo, gli ai 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 ai 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·a1)(a·a2)·…·(a·ak).
“Che puoi scrivere, in forma un po' più abbreviata, così:”.
aka1a2…ak.
“E questa espressione, grazie alla dimostrazione che hai appena fatto, è congruente al prodotto di tutti gli ai”.
“Proprio così. L'espressione finale è questa:”.
aka1a2…ak ≡ a1a2…ak 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 a1a2…ak(ak-1) è multiplo di p. Dato che tutti gli ai sono primi con p, possiamo concludere che è l'espressione ak-1 ad essere multipla di p. E cioè, concludendo:”.
ak ≡ 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”.
martedì 20 aprile 2010
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ì?”.
46·6!
“Perfetto. Te le generalizzo in questo modo:”.
ap-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:”.
ap-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”.
ap-1(p-1)! - (p-1)! è multiplo di p.
“Molto bene. Raccogliendo il fattore comune, possiamo scrivere che:”.
(p-1)!(ap-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 (ap-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à ap-1-1 ad essere multiplo di p”.
“Bene. Quindi possiamo dire che ap-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 ap-1 ≡ 1 mod p”.
“Bello”.
“E questo si chiama piccolo teorema di Fermat”.
“Ce n'è anche uno grande?”.
“Sì, ma questa è un'altra storia”.
“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ì?”.
46·6!
“Perfetto. Te le generalizzo in questo modo:”.
ap-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:”.
ap-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”.
ap-1(p-1)! - (p-1)! è multiplo di p.
“Molto bene. Raccogliendo il fattore comune, possiamo scrivere che:”.
(p-1)!(ap-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 (ap-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à ap-1-1 ad essere multiplo di p”.
“Bene. Quindi possiamo dire che ap-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 ap-1 ≡ 1 mod p”.
“Bello”.
“E questo si chiama piccolo teorema di Fermat”.
“Ce n'è anche uno grande?”.
“Sì, ma questa è un'altra storia”.
lunedì 19 aprile 2010
Alice, Bob e Eva — Esercizi
914 + 924 + 934 + 944 + 954 ≡ x mod 5
“Allora, come va con l'esercizio?”.
“Ehm”.
“Niente?”.
“Mah, no, qualcosa ho fatto, ma mi sfugge la visione globale”.
“Questa scusa devo passarla ai miei studenti”.
“Uffa. Come dovrei procedere?”.
“Comincia a calcolare il resto della divisione per 5 di ognuna delle basi”.
“Ok, questo è facile: 91 dà resto 1 nella divisione per 5, 92 invece 2, e così via”.
“Fino a 95”.
“Sì, giusto: 95 dà resto 0”.
“Benissimo. Ora eleva questi resti alla quarta”.
“Ah, capisco: sto applicando la proprietà delle potenze, vero?”.
“Esatto. Prima ti calcoli a ≡ x mod 5, poi calcoli x4 ≡ y mod 5. Se a ≡ x, anche a4 ≡ x4”.
“Quindi, per capire, dato che 91 ≡ 1 allora 914 ≡ 14?”.
“Esatto. Prosegui con gli altri numeri, adesso”.
“Allora, 92 ≡ 2, quindi 924 ≡ 16”.
“Dato che 16 è maggiore di 5, vai avanti e calcola 16 mod 5”.
“Giusto; risulta ancora 1”.
“Esatto. Vai avanti ancora”.
“Vediamo: 93 ≡ 3, quindi 934 ≡ 81 ≡ 1, poi abbiamo 94 ≡ 4, quindi 944 ≡ 256 ≡ 1, e infine 95 ≡ 0 e quindi 954 ≡ 0”.
“Ottimo. Quindi il risultato della nostra espressione è 4”.
“Bello, anche se non è del tutto immediato”.
“In che senso?”.
“Nel senso che i numeri diventano grossi ugualmente. Insomma, anche se non è un numero gigantesco, 256 è pur sempre un numero di tre cifre”.
“Capisco che sei calcolatrice-dipendente, ma non è necessario arrivare fino a 256. Voglio dire, sai già che 94 ≡ 4, no?”.
“Certo, questo è facile”.
“Allora puoi dire che 944 ≡ 44 ≡ 42·42. Ora i calcoli sono più semplici, no?”.
“In effetti, sì: 42 = 16 ≡ 1, quindi 44 ≡ 12 ≡ 1”.
“Bene. Quindi hai calcolato il resto della divisione per 5 di una espressione senza calcolarne esplicitamente il valore (che, detto per inciso, è un numero abbastanza grande: 374544979)”.
“Niente male”.
“E nota che puoi farlo anche per numeri molto più grandi. Prova questo, per esempio:”.
91100 + 92100 + 93100 + 94100 + 95100 ≡ x mod 5
“Alla cento?”.
“Sì”.
“Ehi, mi stai fregando, io so già che i numeri da 91 a 95 nella congruenza modulo 5 valgono tutti 1, tranne l'ultimo che vale 0”.
“E quindi?”.
“E quindi se elevo 1 alla 100 ottengo sempre 1. Il risultato è 4 anche qui”.
“Benissimo! Visto che la calcolatrice non serve? Ora, però, facciamo un calcolo che non è una fregatura:”.
91100 + 92100 + 93100 + 94100 + 95100 ≡ x mod 7
“Uh, modulo 7, cosa cambia?”.
“Prova a calcolare 91 mod 7”.
“91 è un multiplo di 7, quindi 91 ≡ 0”.
“Questa era facile. Passa al 92”.
“Bè, se 91 ≡ 0, allora 92 ≡ 1. Facile anche questa”.
“Avanti”.
“Non mi sembra così difficile: 93 ≡ 2, facile”.
“Ah, vedo che hai dimenticato che devi poi elevare alla 100. Fino a che si tratta di 0 e di 1, è facile elevarli. Ora però hai a che fare con 2100”.
“Posso usare la calcolatrice?”.
“Ti pare una domanda da fare?”.
“Ok, ok. Allora, come faccio?”.
“Una buona cosa, come hai visto, è quando ottieni un resto uguale a 1”.
“Bene, quindi?”.
“Comincia ad analizzare le potenze di 2, modulo 7”.
“Allora, 21 ≡ 2, 22 ≡ 4, 23 ≡ 8 ≡ 1. Ecco, ho trovato un 1”.
“Bene, ora sai che se prendi tre fattori 2 alla volta ottieni sempre un 1. Quindi come puoi fare per calcolare 2100?”.
“Vediamo, raggruppare a tre alla volta significa dividere per 3, ma 100 non è divisibile per 3, quindi avrò un resto. Cioè, avrò resto 1, giusto?”.
“Sì, in pratica hai calcolato 2100 = 299·2 = (23)33·2 ≡ 133·2 ≡ 2”.
“Ok, allora provo con 3. Vediamo, 32 = 9 ≡ 2, 33 = 27 ≡ 6”.
“Ti potrebbe forse essere d'aiuto notare che 33 ≡ 6 ≡ -1”.
“Meno uno?”.
“Sì, ricordati dell'orologio: se 7 corrisponde a 0, 8 corrisponde a 1, 6 corrisponde a -1”.
“Sì, è vero, mi avevi detto che questi calcoli funzionano anche con i numeri negativi. Ma perché mi è utile?”.
“Perché se 33 ≡ -1, allora 36 ≡ (-1)2 ≡ 1, ed ecco che hai trovato la tua potenza uguale a 1”.
“Perfetto. Allora 3100 può essere scritto come 396·34 ≡ 34 ≡ 81 ≡ 4”.
“Rimane 4100. E ricordati che 4 è una potenza di 2”.
“Giusto, dato che ho scoperto prima che 23 ≡ 1, posso dire che anche 26 ≡ 1. Però 26 = 43, quindi ecco che ho trovato la potenza uguale a 1: 43 ≡ 1”.
“E quindi ora è facile: 499 sarà congruente a 1, e quindi 4100 ≡ 4”.
“E finalmente posso trovare quello che mi hai chiesto: il risultato è 1+2+4+4 = 11 ≡ 4”.
“Senza dover calcolare il numerone”.
“Mh, però c'è qualcosa che non mi convince”.
“Cosa?”.
“Questi calcoli funzionano se riesco a trovare una potenza congruente a 1. Siamo sicuri che la trovo sempre?”.
“Bella domanda”.
“Allora, come va con l'esercizio?”.
“Ehm”.
“Niente?”.
“Mah, no, qualcosa ho fatto, ma mi sfugge la visione globale”.
“Questa scusa devo passarla ai miei studenti”.
“Uffa. Come dovrei procedere?”.
“Comincia a calcolare il resto della divisione per 5 di ognuna delle basi”.
“Ok, questo è facile: 91 dà resto 1 nella divisione per 5, 92 invece 2, e così via”.
“Fino a 95”.
“Sì, giusto: 95 dà resto 0”.
“Benissimo. Ora eleva questi resti alla quarta”.
“Ah, capisco: sto applicando la proprietà delle potenze, vero?”.
“Esatto. Prima ti calcoli a ≡ x mod 5, poi calcoli x4 ≡ y mod 5. Se a ≡ x, anche a4 ≡ x4”.
“Quindi, per capire, dato che 91 ≡ 1 allora 914 ≡ 14?”.
“Esatto. Prosegui con gli altri numeri, adesso”.
“Allora, 92 ≡ 2, quindi 924 ≡ 16”.
“Dato che 16 è maggiore di 5, vai avanti e calcola 16 mod 5”.
“Giusto; risulta ancora 1”.
“Esatto. Vai avanti ancora”.
“Vediamo: 93 ≡ 3, quindi 934 ≡ 81 ≡ 1, poi abbiamo 94 ≡ 4, quindi 944 ≡ 256 ≡ 1, e infine 95 ≡ 0 e quindi 954 ≡ 0”.
“Ottimo. Quindi il risultato della nostra espressione è 4”.
“Bello, anche se non è del tutto immediato”.
“In che senso?”.
“Nel senso che i numeri diventano grossi ugualmente. Insomma, anche se non è un numero gigantesco, 256 è pur sempre un numero di tre cifre”.
“Capisco che sei calcolatrice-dipendente, ma non è necessario arrivare fino a 256. Voglio dire, sai già che 94 ≡ 4, no?”.
“Certo, questo è facile”.
“Allora puoi dire che 944 ≡ 44 ≡ 42·42. Ora i calcoli sono più semplici, no?”.
“In effetti, sì: 42 = 16 ≡ 1, quindi 44 ≡ 12 ≡ 1”.
“Bene. Quindi hai calcolato il resto della divisione per 5 di una espressione senza calcolarne esplicitamente il valore (che, detto per inciso, è un numero abbastanza grande: 374544979)”.
“Niente male”.
“E nota che puoi farlo anche per numeri molto più grandi. Prova questo, per esempio:”.
91100 + 92100 + 93100 + 94100 + 95100 ≡ x mod 5
“Alla cento?”.
“Sì”.
“Ehi, mi stai fregando, io so già che i numeri da 91 a 95 nella congruenza modulo 5 valgono tutti 1, tranne l'ultimo che vale 0”.
“E quindi?”.
“E quindi se elevo 1 alla 100 ottengo sempre 1. Il risultato è 4 anche qui”.
“Benissimo! Visto che la calcolatrice non serve? Ora, però, facciamo un calcolo che non è una fregatura:”.
91100 + 92100 + 93100 + 94100 + 95100 ≡ x mod 7
“Uh, modulo 7, cosa cambia?”.
“Prova a calcolare 91 mod 7”.
“91 è un multiplo di 7, quindi 91 ≡ 0”.
“Questa era facile. Passa al 92”.
“Bè, se 91 ≡ 0, allora 92 ≡ 1. Facile anche questa”.
“Avanti”.
“Non mi sembra così difficile: 93 ≡ 2, facile”.
“Ah, vedo che hai dimenticato che devi poi elevare alla 100. Fino a che si tratta di 0 e di 1, è facile elevarli. Ora però hai a che fare con 2100”.
“Posso usare la calcolatrice?”.
“Ti pare una domanda da fare?”.
“Ok, ok. Allora, come faccio?”.
“Una buona cosa, come hai visto, è quando ottieni un resto uguale a 1”.
“Bene, quindi?”.
“Comincia ad analizzare le potenze di 2, modulo 7”.
“Allora, 21 ≡ 2, 22 ≡ 4, 23 ≡ 8 ≡ 1. Ecco, ho trovato un 1”.
“Bene, ora sai che se prendi tre fattori 2 alla volta ottieni sempre un 1. Quindi come puoi fare per calcolare 2100?”.
“Vediamo, raggruppare a tre alla volta significa dividere per 3, ma 100 non è divisibile per 3, quindi avrò un resto. Cioè, avrò resto 1, giusto?”.
“Sì, in pratica hai calcolato 2100 = 299·2 = (23)33·2 ≡ 133·2 ≡ 2”.
“Ok, allora provo con 3. Vediamo, 32 = 9 ≡ 2, 33 = 27 ≡ 6”.
“Ti potrebbe forse essere d'aiuto notare che 33 ≡ 6 ≡ -1”.
“Meno uno?”.
“Sì, ricordati dell'orologio: se 7 corrisponde a 0, 8 corrisponde a 1, 6 corrisponde a -1”.
“Sì, è vero, mi avevi detto che questi calcoli funzionano anche con i numeri negativi. Ma perché mi è utile?”.
“Perché se 33 ≡ -1, allora 36 ≡ (-1)2 ≡ 1, ed ecco che hai trovato la tua potenza uguale a 1”.
“Perfetto. Allora 3100 può essere scritto come 396·34 ≡ 34 ≡ 81 ≡ 4”.
“Rimane 4100. E ricordati che 4 è una potenza di 2”.
“Giusto, dato che ho scoperto prima che 23 ≡ 1, posso dire che anche 26 ≡ 1. Però 26 = 43, quindi ecco che ho trovato la potenza uguale a 1: 43 ≡ 1”.
“E quindi ora è facile: 499 sarà congruente a 1, e quindi 4100 ≡ 4”.
“E finalmente posso trovare quello che mi hai chiesto: il risultato è 1+2+4+4 = 11 ≡ 4”.
“Senza dover calcolare il numerone”.
“Mh, però c'è qualcosa che non mi convince”.
“Cosa?”.
“Questi calcoli funzionano se riesco a trovare una potenza congruente a 1. Siamo sicuri che la trovo sempre?”.
“Bella domanda”.
venerdì 16 aprile 2010
Alice, Bob e Eva — Qualche proprietà
“Abbiamo dato la definizione di congruenza in modulo, cioè abbiamo spiegato cosa significa la scrittura m ≡ n mod p”.
“Sì, significa che m diviso per p dà resto n”.
“Bene. Ora studiamo qualche proprietà. Per capire come funzionano le cose, prendiamo ad esempio p = 7. Tieni presente che tutto quello che diciamo sarà poi valido per ogni p”.
“Va bene”.
“Allora, per prima cosa: come possiamo scrivere, in un altro modo, la congruenza m ≡ n mod 7?”.
“In che senso, in un altro modo?”.
“Utilizzando simboli già noti in precedenza. In pratica, ti sto chiedendo la definizione in formule”.
“Ah, ok. Bè, vorrebbe dire che quando divido m per 7 ottengo un quoziente che non conosco (e che non mi interessa) e resto n”.
“Puoi chiamare h il quoziente”.
“Allora, potrei scrivere che m = 7h + n”.
“Esatto. Facciamo un esempio, prendiamo due numeri m e n che siano entrambi congrui a 2 modulo 7. Ti scrivo le formule qua, riesci a tradurle?”.
m ≡ 2 mod 7,
n ≡ 2 mod 7.
“Allora, i due quozienti non saranno necessariamente uguali, giusto?”.
“Giustissimo. Uno lo possiamo chiamare h, l'altro k”.
“Allora le due congruenze diventano:”.
m = 7h + 2,
n = 7k + 2.
“Bene. Ora calcola la differenza m-n”.
“Uhm, m-n è uguale a 7h - 7k + 2 - 2. Dato che i 2 si eliminano, risulta che m-n è uguale a 7h - 7k. Ehi, posso raccogliere un 7, quindi ottengo che m-n = 7(h-k). In pratica m-n è un multiplo di 7”.
“Perfetto. Non ti sarà difficile generalizzare in un teorema questa idea di dimostrazione”.
“Mh, no, direi di no. Credo che funzioni così: se due numeri sono congruenti modulo p, allora la loro differenza è un multiplo di p”.
“Giusto, anche se non abbiamo dimostrato proprio questa affermazione. In realtà nell'esempio non abbiamo preso due numeri congruenti tra loro, ma entrambi congruenti a 2”.
“Ah. E quindi?”.
“Quindi va bene lo stesso, perché la congruenza è una relazione di equivalenza”.
“Non ti seguo. Le relazioni di equivalenza sono quelle per le quali valgono quelle tre proprietà: riflessiva, simmetrica e transitiva?”.
“Esatto, sono loro, vedo che ti ricordi qualcosa”.
“E il fatto che la congruenza in modulo è una relazione di equivalenza lo dimostriamo?”.
“Direi di no, non è difficile una volta che hai capito un concetto importante: la congruenza vale anche coi numeri negativi”.
“In che senso?”.
“Possiamo dire che -5 è congruente a 2 modulo 7, perché -5 è uguale a -7 + 2”.
“Ah, non ci avevo pensato. È come se andassimo indietro con l'orologio”.
“Esatto. Se tieni presente questa cosa, puoi dimostrare facilmente che la congruenza è una relazione di equivalenza, e quindi se hai due numeri entrambi congruenti a 2, tanto per fare un esempio, allora essi sono congruenti tra loro”.
“In pratica è come se dicessi che, non so, 15 e 22 sono congruenti tra loro modulo 7 perché entrambi sono congruenti a 1?”.
“Giustissimo, è così. Ora proviamo ad analizzare la somma di due numeri modulo il nostro 7. Prendi questi due:”.
m ≡ 3 mod 7,
n ≡ 5 mod 7.
“Allora, la prima uguaglianza significa che m = 7h + 3, mentre la seconda significa che n = 7k + 5. Se faccio la somma ottengo che m + n = 7(h + k) + 8. Quindi m + n ≡ 8 mod 7. Non mi piace.”.
“Perché?”.
“Perché 8 è maggiore di 7, come fa a venire un resto maggiore del divisore?”.
“Giusto. Ma dato che 8 è uguale a 7+1, puoi togliere 7 da 8 e sommarlo a 7(h + k)”.
“Quindi verrebbe m + n = 7(h + k + 1) + 1”.
“Esatto. In pratica, se nella somma ti risulta un risultato maggiore di 7, puoi farne di nuovo la divisione per 7 e tenere sempre il resto. E poi ricordati che abbiamo esteso il concetto di congruenza: quella relazione ci dice che sia m + n che 8 hanno lo stesso resto quando vengono divisi per 7 (cioè 1)”.
“Ho capito. Quindi questo secondo teorema diventerebbe così: se a ≡ b mod p e c ≡ d mod p, allora a + c ≡ b + d mod p”.
“Sì. Detto in termini meno rigorosi: possiamo fare le somme come ci pare”.
“Oh, mi piacciono questi enunciati decisi”.
“Già che ci siamo, facciamo anche la moltiplicazione. Prendiamo per esempio m ≡ 3 e n ≡ 5”.
“Vado, provo a fare tutti i conti. Allora, prima di tutto le tue uguaglianze significano questo:”.
m = 7h + 3,
n = 7k + 5.
“Bene. Io non l'avevo specificato, ma stiamo sempre immaginando che p sia uguale a 7”.
“Sì. Ora moltiplico:”.
mn = (7h + 3)(7k + 5) = … + 15.
“Come mai hai messo i puntini?”.
“Perché tanto l'espressione sottointesa dai puntini contiene sempre multipli di 7”.
“Quindi?”.
“Quindi posso scriverla così: mn = 7t + 15. In fondo a me interessa il 15, non ciò che moltiplica 7”.
“Molto bene. Quindi alla fine abbiamo capito come funziona la moltiplicazione?”.
“Sì, il teorema dovrebbe essere questo: se a ≡ b mod p e c ≡ d mod p, allora ac ≡ bd mod p”.
“Oppure, in termini non rigorosi?”.
“Possiamo fare le moltiplicazioni come ci pare”.
“Caso particolare: a = c. Che succede?”.
“Uh, le potenze. Bè, se a = c allora posso sostituire e dire che a2 ≡ b2 mod p”.
“Bene, e naturalmente possiamo moltiplicare a per sé stesso più volte, e generalizzare la regola sulle potenze in questo modo:”.
se a ≡ b mod p, allora an ≡ bn mod p, per ogni n naturale.
“Bello, anche le potenze si comportano bene”.
“Sì, anche loro. Per oggi basta, ti lascio un esercizio: che resto si ottiene dividendo per 5 la seguente espressione?”.
914 + 924 + 934 + 944 + 954.
“Sì, significa che m diviso per p dà resto n”.
“Bene. Ora studiamo qualche proprietà. Per capire come funzionano le cose, prendiamo ad esempio p = 7. Tieni presente che tutto quello che diciamo sarà poi valido per ogni p”.
“Va bene”.
“Allora, per prima cosa: come possiamo scrivere, in un altro modo, la congruenza m ≡ n mod 7?”.
“In che senso, in un altro modo?”.
“Utilizzando simboli già noti in precedenza. In pratica, ti sto chiedendo la definizione in formule”.
“Ah, ok. Bè, vorrebbe dire che quando divido m per 7 ottengo un quoziente che non conosco (e che non mi interessa) e resto n”.
“Puoi chiamare h il quoziente”.
“Allora, potrei scrivere che m = 7h + n”.
“Esatto. Facciamo un esempio, prendiamo due numeri m e n che siano entrambi congrui a 2 modulo 7. Ti scrivo le formule qua, riesci a tradurle?”.
m ≡ 2 mod 7,
n ≡ 2 mod 7.
“Allora, i due quozienti non saranno necessariamente uguali, giusto?”.
“Giustissimo. Uno lo possiamo chiamare h, l'altro k”.
“Allora le due congruenze diventano:”.
m = 7h + 2,
n = 7k + 2.
“Bene. Ora calcola la differenza m-n”.
“Uhm, m-n è uguale a 7h - 7k + 2 - 2. Dato che i 2 si eliminano, risulta che m-n è uguale a 7h - 7k. Ehi, posso raccogliere un 7, quindi ottengo che m-n = 7(h-k). In pratica m-n è un multiplo di 7”.
“Perfetto. Non ti sarà difficile generalizzare in un teorema questa idea di dimostrazione”.
“Mh, no, direi di no. Credo che funzioni così: se due numeri sono congruenti modulo p, allora la loro differenza è un multiplo di p”.
“Giusto, anche se non abbiamo dimostrato proprio questa affermazione. In realtà nell'esempio non abbiamo preso due numeri congruenti tra loro, ma entrambi congruenti a 2”.
“Ah. E quindi?”.
“Quindi va bene lo stesso, perché la congruenza è una relazione di equivalenza”.
“Non ti seguo. Le relazioni di equivalenza sono quelle per le quali valgono quelle tre proprietà: riflessiva, simmetrica e transitiva?”.
“Esatto, sono loro, vedo che ti ricordi qualcosa”.
“E il fatto che la congruenza in modulo è una relazione di equivalenza lo dimostriamo?”.
“Direi di no, non è difficile una volta che hai capito un concetto importante: la congruenza vale anche coi numeri negativi”.
“In che senso?”.
“Possiamo dire che -5 è congruente a 2 modulo 7, perché -5 è uguale a -7 + 2”.
“Ah, non ci avevo pensato. È come se andassimo indietro con l'orologio”.
“Esatto. Se tieni presente questa cosa, puoi dimostrare facilmente che la congruenza è una relazione di equivalenza, e quindi se hai due numeri entrambi congruenti a 2, tanto per fare un esempio, allora essi sono congruenti tra loro”.
“In pratica è come se dicessi che, non so, 15 e 22 sono congruenti tra loro modulo 7 perché entrambi sono congruenti a 1?”.
“Giustissimo, è così. Ora proviamo ad analizzare la somma di due numeri modulo il nostro 7. Prendi questi due:”.
m ≡ 3 mod 7,
n ≡ 5 mod 7.
“Allora, la prima uguaglianza significa che m = 7h + 3, mentre la seconda significa che n = 7k + 5. Se faccio la somma ottengo che m + n = 7(h + k) + 8. Quindi m + n ≡ 8 mod 7. Non mi piace.”.
“Perché?”.
“Perché 8 è maggiore di 7, come fa a venire un resto maggiore del divisore?”.
“Giusto. Ma dato che 8 è uguale a 7+1, puoi togliere 7 da 8 e sommarlo a 7(h + k)”.
“Quindi verrebbe m + n = 7(h + k + 1) + 1”.
“Esatto. In pratica, se nella somma ti risulta un risultato maggiore di 7, puoi farne di nuovo la divisione per 7 e tenere sempre il resto. E poi ricordati che abbiamo esteso il concetto di congruenza: quella relazione ci dice che sia m + n che 8 hanno lo stesso resto quando vengono divisi per 7 (cioè 1)”.
“Ho capito. Quindi questo secondo teorema diventerebbe così: se a ≡ b mod p e c ≡ d mod p, allora a + c ≡ b + d mod p”.
“Sì. Detto in termini meno rigorosi: possiamo fare le somme come ci pare”.
“Oh, mi piacciono questi enunciati decisi”.
“Già che ci siamo, facciamo anche la moltiplicazione. Prendiamo per esempio m ≡ 3 e n ≡ 5”.
“Vado, provo a fare tutti i conti. Allora, prima di tutto le tue uguaglianze significano questo:”.
m = 7h + 3,
n = 7k + 5.
“Bene. Io non l'avevo specificato, ma stiamo sempre immaginando che p sia uguale a 7”.
“Sì. Ora moltiplico:”.
mn = (7h + 3)(7k + 5) = … + 15.
“Come mai hai messo i puntini?”.
“Perché tanto l'espressione sottointesa dai puntini contiene sempre multipli di 7”.
“Quindi?”.
“Quindi posso scriverla così: mn = 7t + 15. In fondo a me interessa il 15, non ciò che moltiplica 7”.
“Molto bene. Quindi alla fine abbiamo capito come funziona la moltiplicazione?”.
“Sì, il teorema dovrebbe essere questo: se a ≡ b mod p e c ≡ d mod p, allora ac ≡ bd mod p”.
“Oppure, in termini non rigorosi?”.
“Possiamo fare le moltiplicazioni come ci pare”.
“Caso particolare: a = c. Che succede?”.
“Uh, le potenze. Bè, se a = c allora posso sostituire e dire che a2 ≡ b2 mod p”.
“Bene, e naturalmente possiamo moltiplicare a per sé stesso più volte, e generalizzare la regola sulle potenze in questo modo:”.
se a ≡ b mod p, allora an ≡ bn mod p, per ogni n naturale.
“Bello, anche le potenze si comportano bene”.
“Sì, anche loro. Per oggi basta, ti lascio un esercizio: che resto si ottiene dividendo per 5 la seguente espressione?”.
914 + 924 + 934 + 944 + 954.
giovedì 15 aprile 2010
Alice, Bob e Eva — L'orologio
“Che ore saranno tra 314 ore?”.
“Eh? Boh, devo fare il conto, non so”.
“Fai il conto, allora”.
“Uhm, 314 ore, ci sono 24 ore in un giorno, 314 diviso 24 fa 13.08(3)”.
“E quindi?”.
“E quindi 314 ore sono un po' più di 13 giorni”.
“Vabbé, ma se vuoi sapere che ore saranno con precisione?”.
“Uhm, allora, rimane un resto di zero virgola zero otto tre periodico…”.
“Che non è propriamente un resto”.
“Eh?”.
“Eh, no. Non è il resto della divisione che hai fatto. Hai presente la regola per la divisione che hai imparato alle elementari?”.
“Uh, quella! Da quanto tempo non ne faccio una. Eccola qua:”.
“Oh, bene. Quindi vedi che 314 diviso 24 ti dà come quoziente 13 e come resto 2. Quello che ti interessa, ai fini della risposta alla mia domanda, è proprio il resto”.
“Ah, ho capito: 314 ore corrispondono a 13 giorni e 2 ore, quindi per sapere che ore saranno devo guardare l'orologio adesso e aggiungere 2 ore. Facile”.
“Benissimo. Il calcolo che hai fatto potrebbe essere scritto anche in questo modo: 314 = 13·24 + 2”.
“Vero”.
“I Veri Matematici lo scrivono anche così: 314 ≡ 2 mod 24”.
“Eh?”.
“Significa che 314 e 2 danno lo stesso resto nella divisione per 24; il resto è naturalmente 2, che è minore di 24. Si legge in questo modo: 314 è congruente (o congruo) a 2 modulo 24”.
“Manca però il 13, il quoziente della divisione”.
“Quello non ci interessa molto. Quando siamo interessati di più ai resti che ai quozienti, utilizziamo questo tipo di scrittura. Ed entriamo nel cosiddetto campo dell'aritmetica modulare”.
“Che non è altro che un modo pomposo per definire l'aritmetica dell'orologio, a quanto vedo”.
“Bè, sì, l'aritmetica dell'orologio è l'aritmetica modulo 24, ma naturalmente possiamo scegliere qualunque numero come base per i nostri moduli”.
“E questo è interessante?”.
“Certo”.
“Voglio dire, serve a qualcosa?”.
“Stranamente, sì. Non che ai Veri Matematici questo fatto interessi molto, però l'aritmetica modulare ha una effettiva applicazione pratica. Praticamente quotidiana”.
“Eh? Boh, devo fare il conto, non so”.
“Fai il conto, allora”.
“Uhm, 314 ore, ci sono 24 ore in un giorno, 314 diviso 24 fa 13.08(3)”.
“E quindi?”.
“E quindi 314 ore sono un po' più di 13 giorni”.
“Vabbé, ma se vuoi sapere che ore saranno con precisione?”.
“Uhm, allora, rimane un resto di zero virgola zero otto tre periodico…”.
“Che non è propriamente un resto”.
“Eh?”.
“Eh, no. Non è il resto della divisione che hai fatto. Hai presente la regola per la divisione che hai imparato alle elementari?”.
“Uh, quella! Da quanto tempo non ne faccio una. Eccola qua:”.
“Oh, bene. Quindi vedi che 314 diviso 24 ti dà come quoziente 13 e come resto 2. Quello che ti interessa, ai fini della risposta alla mia domanda, è proprio il resto”.
“Ah, ho capito: 314 ore corrispondono a 13 giorni e 2 ore, quindi per sapere che ore saranno devo guardare l'orologio adesso e aggiungere 2 ore. Facile”.
“Benissimo. Il calcolo che hai fatto potrebbe essere scritto anche in questo modo: 314 = 13·24 + 2”.
“Vero”.
“I Veri Matematici lo scrivono anche così: 314 ≡ 2 mod 24”.
“Eh?”.
“Significa che 314 e 2 danno lo stesso resto nella divisione per 24; il resto è naturalmente 2, che è minore di 24. Si legge in questo modo: 314 è congruente (o congruo) a 2 modulo 24”.
“Manca però il 13, il quoziente della divisione”.
“Quello non ci interessa molto. Quando siamo interessati di più ai resti che ai quozienti, utilizziamo questo tipo di scrittura. Ed entriamo nel cosiddetto campo dell'aritmetica modulare”.
“Che non è altro che un modo pomposo per definire l'aritmetica dell'orologio, a quanto vedo”.
“Bè, sì, l'aritmetica dell'orologio è l'aritmetica modulo 24, ma naturalmente possiamo scegliere qualunque numero come base per i nostri moduli”.
“E questo è interessante?”.
“Certo”.
“Voglio dire, serve a qualcosa?”.
“Stranamente, sì. Non che ai Veri Matematici questo fatto interessi molto, però l'aritmetica modulare ha una effettiva applicazione pratica. Praticamente quotidiana”.
sabato 3 aprile 2010
Iscriviti a:
Post (Atom)