UNA “NUOVA” ARITMETICA
L’ ARITMETICA MODULARE
e
SISTEMI di NUMERAZIONE
Generalmente ci serviamo dell’orologio o della sveglia molte volte al giorno. I nostri
orologi sono macchine per misurare il tempo e, qualsiasi strumento di misura è di
“natura” matematica.
Contando con i numeri che rappresentano le ore, spesso si ottengono risultati
insoliti: sono le 7 e aggiungiamo 8 ore
11
0
1
10
2
9
3
4
8
7
…….
5
7+8=3
Si legge “7 più 8 uguale a 3 (modulo 12) “
6
Questo tipo di aritmetica si chiama aritmetica modulare o anche sistema
di numerazione finito
Un’ altro sistema numerico finito si può costruire con i giorni della
settimana: 0 domenica, 1 lunedì, 2 martedì,……, 6 sabato.
alcune domande:
1. Se il 4 marzo era di sabato, che giorno era il 24 marzo?
2. Per trovare che giorno sarà il 4 marzo dell’anno successivo si potrebbe
ragionare così…
3.Si può anche andare all’indietro e chiedersi: che giorno era il 4 marzo del 1906?
E il 4 marzo del 1806?
il problema si può risolvere contando o con l’aritmetica modulo 7
Allo stesso modo si possono risolvere problemi del tipo: che ora sarà tra 1675 ore?
Spiegazione parziale
Se numeriamo le 24 ore del giorno da 0 a 23 e se, ora sono le 18,tra 1675 ore
saranno (1675+18) mod 24, cioè le 11.
Il gioco del telefono
-Scrivi il tuo numero di
telefono
-Cambia l’ordine alle cifre e
riscrivi il numero ottenuto
-Sottrai dal maggiore il
minore e somma le cifre
fino ad ottenere un numero
con un’unica cifra
-Inizia a contare dopo la
stella (contrassegnata con 1)
nel senso indicato
Quale posto raggiungi?
1
il gioco del telefono
Un numero è divisibile per 9 se lo è la somma delle sue cifre:
esempio
un numero di tre cifre (a, b, c) assegnato, si scrive in forma polinomiale nel
modo seguente :
(100 a + 10 b + c) = (99 + 1) a + (9 +1 ) b + c = 99 a + 9 b + (a + b + c ) =
= 9 ( 11 a + 1 b ) +( a + b + c )
questa quantità è
divisibile per 9
il numero dato è divisibile per 9, se lo è il termine ( a + b + c )
cioè la somma delle sue cifre
Se il numero di telefono, diviso 9, dà come resto 0, 1 , ……. 8, si ha lo stesso
resto anche con il numero ottenuto cambiando l’ordine alle cifre
la differenza tra i due numeri, divisa per 9, dà come resto la differenza dei
due resti, cioè 0.
I simboli del cerchio sono nove, perciò il conteggio deve terminare sul nono
simbolo dopo il primo indicato .
Consideriamo l’insieme dei numeri interi Z e la relazione detta di congruenza
modulo n (con n > 0), così definita:
Due numeri a e b sono equivalenti modulo n se e solo se (a-b) è
multiplo di n.
Con la relazione di equivalenza si può costruire l’insieme Zn delle classi di
equivalenza, dette anche classi di resto modulo n
classi [0]
[1]
[2]
[3]
[4]
[0] ={0, 5, 10, 15, 20, 25, 30 ……}
[1] ={1, 6, 11, 16, 21, 26, 31 ……..}
[2] ={2, 7, 12, 17, 22, 27, 32 ……..}
[3] ={3, 8, 13, 18, 23, 28, 33 ……..}
[4] ={4, 9, 14, 19, 24, 29, 34 …….}
E’ interessante vedere che le ordinarie operazioni di addizione e moltiplicazione che
sono definite in Z danno luogo a operazioni analoghe in Zn
CLASSE di RESTI MODULO 5
- L’operazione + è interna
- Vale la proprietà associativa
+
[0] [1] [2] [3] [4]
[0]
[0]
[1]
[2]
[3]
[4]
[1]
[1]
[2]
[3]
[4]
[0]
- Esiste , per ogni elemento il
simmetrico
[2]
[2]
[3]
[4]
[0]
[1]
- L’insieme Z5 è chiuso rispetto
alla somma
[3]
[3]
[4]
[0]
[1]
[2]
[a]+ [b] =[a+b]
[4]
[4]
[0]
[1]
[2]
[3]
- Esiste l’elemento neutro [0]
esercizio. [ 2 ] + [ 4 ] = [ 2 + 4 ] = [ 1 ];
la classe [2] rappresenta tutti gli elementi del tipo 2+5h, gli elementi della classe [4] sono
del tipo 4+5k,
la loro somma è 2+5h+4+5k=2+4+5(h+k)=6+5(h+k)= 1+5+5(h+k)=1+5(h+k+1) :questo elemento
appartiene alla classe [1].
CLASSE di
RESTI MODULO 5
- L’operazione * è
interna
*
[0]
[1]
[2]
[3]
[4]
- Vale la proprietà
associativa
[0]
[0]
[0]
[0]
[0]
[0]
-La classe [0] annulla
qualunque prodotto
[1]
[0]
[1]
[2]
[3]
[4]
[2]
[0]
[2]
[4]
[1]
[3]
[3]
[0]
[3]
[1]
[4]
[2]
[4]
[0]
[4]
[3]
[2]
[1]
- Esiste l’elemento
neutro [1]
- Esiste , per ogni
elemento, diverso da
[0] il simmetrico
es. [ 2 ] x = [ 3 ]; x = [3] *[2]simmetico ;
x =[3] * [3];
x = [4]
CLASSE di RESTI MODULO 6
Qui molte proprietà non valgono:
*
[0]
[1]
[2]
[3]
[4]
[5]
- Non è vero che ogni elemento ha
il simmetrico: per i numeri2, 3, 4
non esistono
[0]
[0]
[0]
[0]
[0]
[0]
[0]
[1]
[0]
[1]
[2]
[3]
[4]
[5]
- Ci sono elementi diversi da zero
che moltiplicati tra loro danno 0
[2]
[0]
[2]
[4]
[0]
[2]
[4]
[3]
[0]
[3]
[0]
[3]
[0]
[3]
- In alcune righe compare più
volte uno stesso elemento
[4]
[0]
[4]
[2]
[0]
[4]
[2]
[5]
[0]
[5]
[4]
[3]
[2]
[1]
Cosa è cambiato da 5 a 6? Si potrebbe rispondere che 5 è dispari e 6 pari, ma
basterebbe provare con modulo 9 o 15 per rendersi conto che alcuni elementi non
hanno il simmetrico.
5 è un numero primo e non ammette divisori propri e quindi non ci possono essere
numeri diversi da zero che moltiplicati tra loro diano 0
La prova del nove
Supponiamo di aver moltiplicato due numeri a e b, e di aver ottenuto come risultato
c. Rifacendo il calcolo, potremmo ottenere risultati uguali o diversi: se sono diversi
siamo sicuri che almeno uno dei due è errato, se sono uguali non abbiamo la
certezza che il risultato sia corretto perché potremmo aver fatto lo stesso errore
in tutti due i calcoli.
Lo stesso avviene con la prova del nove: se i conti “non tornano” siamo sicuri di aver
sbagliato la prova o la moltiplicazione, se “tornano”, avremo la conferma
dell’esattezza del risultato, ma mai la sicurezza
La prova del nove è molto più veloce che non rifare la moltiplicazione e quindi è
preferibile
La prova del nove ( o dell’ 11, o ... ) si basa sul fatto che se a * b = c allora
a mod p * b mod p = c mod p
Es. 564 * 4318 = 2435352
a mod p
c mod p
a mod p * b mod p
c mod p = 6
7
*
b mod p
6
(6 7) mod 9 = 6
Si potrebbe fare anche la prova del 2, ricordando che a mod 2 è uguale a 1 se a è
dispari e a 0 se a è pari
Se almeno uno dei due numeri da moltiplicare è pari il risultato deve essere pari, se
ambedue sono dispari il risultato deve essere dispari
Perché allora non si usa la prova del 2 ?
Ricordiamo che se la prova non torna il risultato è sbagliato, ma se la prova torna,
potrebbe funzionare per caso.
E perché non si fa con 347? Ci sarebbero 347 casi possibili (0……346) e l’eventualità
che la prova torni per caso è piuttosto remota.
La prova del 9 è abbastanza facile, ma anche la prova dell’ 11 può essere applicata
senza troppi problemi
PROVATE
Basta osservare che: 10 = - 1 mod 11; 100 = 10*10 = 1 mod 11
e così via
Anche la prova della divisione ( con resto ) si fa allo stesso modo
Se (a : b ) dà come quoziente q e resto r, risulta q* b +r =a
PROVATE
Il problema del falsario
Alla ricerca di un falsario che spaccia monete, la polizia ha fermato sei
viaggiatori provenienti dal paese di …… , a ognuno dei quali ha sequestrato le
monete e ha fatto sei mucchietti.
La polizia sa solo che le monete false si riconoscono da quelle vere perché
differiscono da queste di un grammo e che le monete buone pesano un numero
esatto di grammi.
Con l’aiuto di una bilancia la polizia riesce a smascherare il falsario
Quante pesate al minimo si devono fare?
Una sola pesata è sufficiente
La strategia consiste nel prendere 1 moneta dal primo mucchio, 2 dal secondo, …6
dall’ultimo mucchio: in totale ci sono 21 monete.
Sia p il peso non noto di una moneta buona. Se tutte le monete fossero buone il
peso totale sarebbe 21p, un numero divisibile per 21.
Invece nel mucchio ci sono monete false, e precisamente una se il falsario è il
primo viaggiatore, due se è il secondo, …… di 6 se è il sesto.
Continuazione ……
Supponiamo che le monete false pesino 1 grammo di più delle buone:
Il peso totale delle 21 monete sarà 21p più tanti grammi quante sono le monete
false
Se si divide il peso totale per 21, si avrà come resto 1 se il falsario è il primo
viaggiatore ……
Che succederebbe se le monete false pesassero 1 in meno ?
Indizio
21p-1
21p
Resto della divisione per 21 è…??
21p+1
Resto della divisione per 21 è 1
Nell’ambito delle classi di resto è interessante il
TEOREMA : Se p è primo, e a è primo con p, a
Fermat)
p – 1=1
mod p (piccolo teorema di
Nel 1736 fu proprio Eulero a generalizzare il piccolo teorema di Fermat e a
dimostrare che
Dati due qualsiasi numeri primi m ed N primi tra loro allora è m (N ) _ 1 = 0 (mod N)
(N): funzione di Eulero che associa, a un numero intero N, il numero degli interi primi con N ed è uno
degli ingredienti fondamentali del cifrario RSA (Rivest, Shamir,Adlemann)
Il teorema permette di calcolare l’inverso di un numero in un’ aritmetica finita
Il problema di codificare o cifrare un messaggio è stato affrontato, generalmente
per usi militari, attraverso tutta la storia della civiltà umana
La sfida del XX secolo era l’ideazione di un codice per cui anche il più potente
calcolatore impiegasse millenni per la decodifica
LA CRITTOGRAFIA A CHIAVE PUBBLICA
(qualche considerazione)
Nel 1976 Diffie e Hellmann riuscirono a mostrare che per scambiarsi un
messaggio segreto non è più indispensabile incontrarsi in privato per fissare una
chiave
Lo sviluppo delle loro idee ha portato alla costruzione di molteplici algoritmi per il
controllo dell’identità digitale – firma – e per la comunicazione cifrata
L’ idea si basa sullo studio degli elevamenti a potenza nelle classi di resto che
permettono ai due comunicanti di accordarsi su una chiave comune con cui
cifrare i propri messaggi
I due interlocutori A e B concordano un numero primo p molto grande e un
intero g minore di p
A sceglie un numero segreto a, calcola  = ga (mod p) e lo comunica a B
A sua volta B sceglie un numero segreto b , calcola = gb (mod p) e lo comunica
ad A
Sarà possibile per A calcolare s =  = gab ( mod p ) e per B calcolare lo stesso
s =  = gab ( mod p )
Chi avesse intercettato a tutta la comunicazione, sarà in possesso dei numeri p,
g, , , ma non conoscendo né a né b , non sarà in grado di calcolare s, perché
nelle classi di resto non si conoscono algoritmi efficienti per calcolare per
esempio a da g e 
Es:p=23, g=5 A sceglie il valore segreto 7 e calcola 57 mod 23=17.
Anche B sceglie un valore segreto, ad esempio, 5, calcola 55 mod 23 = 20
A e B si comunicano i risultati: la chiave comune sarà 175 mod 23 per B che è
uguale a quello che si ricava A, 207 mod 23, ovvero 21.
Il loro segreto in comune è 21
Chi ha ascoltato la conversazione conosce il 23, il 5, il 17 e il 20, ma per
ricavare il segreto comune deve scoprire almeno uno degli esponenti scelti
segretamente e mai comunicati
Nell’esempio si può procedere per tentativi provando gli esponenti da 1 a 22,
ma se i numeri fossero dell’ordine del miliardo di miliardi,( con un miliardo di
combinazioni al secondo), si impiegherebbe un tempo troppo lungo per
decodificare il messaggio
L’aritmetica modulare è usata in numerosi crittosistemi per dissimulare
ulteriormente l’informazione già trasformata da una funzione di cifratura.
P
0
1
2
3
4
C=P3
0
1
8
27
64
0 1
8
5
9
C ’ = P3 mod 11
5
6
125 216
4
7
7
8
9
10 ….
343
512
729
1000 …
2
6
3
10 ….
L’ utilità dell’aritmetica modulare è mostrata già dalla semplice funzione di
cifratura C = P3.
Al crescere di P, la crescita continua di P3 rende possibile invertire la funzione,
ovvero determinare il valore di P che corrisponde a un dato valore di C, anche senza
una formula semplice per esprimere P come radice cubica di C.
Più precisamente, un valore di P che fornisca un valore piccolo di C è esso
stesso piccolo, uno che dia luogo a un valore elevato è elevato.
Se invece si introduce la modularità, C ‘ è uguale a P3 modulo 11, e i valori della
funzione hanno un andamento disordinato.
Al crescere di P, C ‘ varia in modo affatto discontinuo, celando efficacemente P.
SISTEMI di NUMERAZIONE
Per sistema di numerazione si intende quell’ insieme di simboli
e di regole che permettono di esprimere graficamente i numeri
e di leggerli.
A
Contiamo gli elementi dell’ insieme A
nel sistema a base 10
(o modulo 10)
1 * 10 + 4 * 1 = 14
Una decina
4 unità
Ogni numero può essere scritto in forma polinomiale
es.
124 = 1 * 102 + 2 * 101 + 4 * 00 ;
ricordiamo che 10 0 = 1
ALCUNE BASI di NUMERAZIONE DIVERSE DA DIECI
Per gli antichi guerrieri, che dovevano reggere un’arma, forse era più comodo
utilizzare una sola mano e quindi contare a gruppi di cinque, cioè in base cinque:
questo modo di contare è citato per esempio nell’ Odissea di Omero
Gli antichi Caldei, grandi astronomi, divisero il cerchio dell’orizzonte in
trecentossesanta parti e presero il suo sottomultiplo sessanta come base della loro
numerazione.
I Babilonesi usarono delle basi diverse di numerazione, sessanta e dieci.
La numerazione binaria, cioè in base due, era già stata usata da qualche antico
popolo orientale, forse suggerita dall’uso delle due mani; fu poi riutilizzata da G.
Leibniz (1646-1716) nel ‘600, ma ebbe poca fortuna fino a poco tempo fa, quando
divenne la numerazione fondamentale per le macchine calcolatrici.
Nel sistema decimale sono sufficienti dieci simboli : 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 per
rappresentare tutti i numeri
Con lo stesso simbolo possiamo indicare le unità (I ordine), le decine (II ordine), poi
le centinaia (III ordine), etc.
Possiamo usare lo stesso metodo per contare in una base diversa
Se vogliamo contare in base cinque, sono sufficienti cinque simboli (0, 1, 2, 3, 4)
per indicare le unità del I ordine, con un gruppo di cinque “oggetti”(cinquina)
otteniamo un’unità del II ordine, con cinque cinquine formiamo un’ unità del III
ordine e così via.
es.1 Contiamo a base 10
Esempi
103
102
101
Possiamo scrivere 2*101 + 5*100
100
25 dieci
Contiamo a base 5
es.2
53
52
51
Possiamo scrivere 4*51 + 3*50
50
43 cinque
Contiamo in base due
es.3
1
*
1
0
0
1
23
22
21
20
23 + 0
*
22 + 0
*
21 + 1
*
20
1001due
(si legge “uno-zero-zero-uno”)
Contiamo in base due
es.3
23
22
1 * 23 + 0* 22 + 0* 21 + 1* 20
21
20
1001due
(si legge “uno-zero-zero-uno”)
ancora esempi.....
Da una base qualunque alla base 10
e viceversa
32otto = 3 * 81 + 2 * 80 = 24 + 2 = 26dieci
122quattro = 1 * 42 + 2 * 41 + 2 * 40 = 26dieci
Da una base a una base qualunque
23cinque
13dieci
+
0
0
0
1
1
1
10
111tre
Tabelle relative
all’addizione e alla
moltiplicazione a base 2
*
0
0
0
1
0
1
1
qualche operazione .....
a) 120tre + 12tre = 202
b) 121
tre
- 11tre
c) 217otto * 32otto
tre
= 110tre
= 7206otto
d) 11110due : 101due
= 110due
e) AB3sedici + 8ADsedici = 1360sedici
f) 324cinque * 12cinque
= 4443cinque
Ci sono errori ???
È ora di smetterla con questa
matematica, che ne dite?
7
10
13
6