TPSIT – Crittografia – aritmetica modulare

Pubblicato il 17 Dicembre 2018 da admin

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 che 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!

Questa voce è stata pubblicata in Senza categoria. Contrassegna il permalink.

Lascia un commento Annulla risposta