TPSIT – Crittografia – aritmetica modulare

L’algebra modulare si basa sul concetto di congruenza modulo m

a mod m = resto della divisione a/m

Dati tre numeri a, b, m con m\neq 0 si dice cha a e b sono congruenti modulo m, se la differenza a-b è multiplo di m.

De Chirico

a\equiv b\;mod\;m

si può anche scrivere

a\;mod\;m=b\;mod\; m

si legge a è congruo a b modulo m

Invarianza rispetto alle operazioni aritmetiche

Prima proprietà (somma)

[(a\;mod\;m) + (b\;mod\;m)] mod\;m = (a+b)\;mod\;m

(a\;mod\;m+b\;mod\;m)\equiv (a+b)mod\;m

Seconda proprietà (differenza)

[(a\;mod\;m)-(b\;mod\;m)]\;mod\;m=(a-b)\;mod\;m

(a\;mod\;m-b\;mod\;m)\equiv (a-b)\;mod\;m

Terza proprietà (prodotto)

[(a\;modm)\;\cdot(b\;mod\;m)]\;mod\;m=(a\cdot\;b)\;mod\;m

(a\;mod\;m\cdot b\;mod\;m)\equiv (a\cdot b)mod\;m

Quarta proprietà (potenza–> generalizzazione del prodotto)

\left [ \left ( a \;mod\; m \right )^{k} \right ]\;mod \; m = a^{k} \; mod \; m

\left [ \left ( a \;mod\; m \right )^{k} \right ]\equiv a^{k} \; mod \; m

Esempi

Calcolo che si farebbe in assenza della conoscenza delle proprietà

540\; mod\;17 = ?
540 / 17 = 31,764….
31\cdot 17 = 527 540 -527 = 13

Applicazione della proprietà della somma

(6+7) \;mod\;5 = 3
(6\; mod\;5 + 7\; mod\;5) mod\;5= (1 + 2)\; mod\;5 = 3

Conseguenza dell’ultima proprietà

Ad esempio:

\left [ \left ( 9 \;mod\; 5 \right )^{2} \right ]\;mod \; 5 = 4^{2} \; mod \; 5= 16 \: mod \; 5 =1

ed è uguale a:

9^{2} \; mod \; 5= 81 \: mod \; 5 =1

Ho semplificato di molto il calcolo

Approfondimenti sull’algebra modulare

Molte funzioni normalmente invertibili, diventano non invertibili nella versione modulare

Esempio: il logaritmo

a^{b}=c

invertendola ho appunto la definizione di logaritmo e posso trovare il valore dell’esponente b:

b=\log _{a}c

MA (DEFINIZIONE DI LOGARITMO DISCRETO)

a^{b}\; mod \; m=c

Trovare b dati a, c ed m è computazionalmentemolto difficile!

This entry was posted in Senza categoria. Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *