.   .   .   C   i   p   h   e   r   t   e   x   t   .   .   .

.   .   .   C   i   p   h   e   r   t   e   x   t   .   .   .

 

Riassunto di algebra modulare

Vengono riportate di seguito alcune delle regole base dell'algebra modulare, la cui conoscenza e' richiesta per la comprensione di alcune delle operazioni e delle definizioni impiegate nelle pagine di questo sito. Questo riassunto tuttavia puo' solo servire di richiamo per chi possiede gia' la conoscenza degli argomenti trattati o comunque delle buone basi, ma non e' consigliato come testo per lo studio di tali argomenti.

---

 

 

Numeri primi

Sono tutti quei numeri divisibili solo per 1 e per se stessi. Indicati con p.

Tutti gli altri numeri interi (composti) sono derivabili dai numeri primi come prodotto. (Th. Fond. aritmetica).

 

Numeri coprimi
 

Due numeri sono coprimi se il massimo comun divisore(MCD) tra loro e’ 1.

Nota:

0 non e’ primo e non e’ coprimo con nulla.

Modulo

A mod m = r significa che Km + r = a

Nota:

amod0 = a

0mod0 = 0

0modm = 0

Regola cerchio:

 

ES)

3mod7 = 3 (3<7)

-1mod7 = 6 (Per regola cerchio)

7mod3 = 1

 

 

 

Congruenza

 

[a mod m] e' congruente a  [b mod m] se entrambi danno il medesimo risultato.

ES)

13mod3 = 1

22mod3 = 1

 Sono congruenti.

 

MCD: Algoritmo di Euclide

MCD(a,b) = MOD(b mod a, a) . Applicare in modo ricorsivo.

ES)

MCD(12,18) = MCD(18mod12, 12) = MCD(6, 12) = MCD(12mod6, 6) = MCD(0, 6) = 6.

 

Cardinalita’

L’insieme Zn (completo) comprende tutti I numeri dell’insieme da 0 (n-1).

L’insieme Zn* (ridotto) comprende solo i numeri coprimi con n di Zn completo.

ES)

M=21 = 7*3

φ(M) = 6*2=12

φ(m) = П(i da 1 a m) (P(i) ^ h(i) – P(i)^h(i-1))

ES)

φ(60) = [60= 2^2 * 3 * 5] = (3-1)(5-1)(2^2 - 2^1).

 

Logaritmo

(a^x) mod m = b significa che x = log _DIGa (b). [Log digitale: prendere solo intero di risultato, senza approssimazioni]

 

Square & Multiply

Per calcolare il mod di un numero elevato a potenza, si utilizza il metodo Square & Multiply:

Si codifica l’esponente in binario.

Si pone la cifra in binario in verticale dal most al less sign. Byte.

Ad ogni riga:

• se c’e’ 1, si eleva al quadrato il numero risultante dalla riga superiore (se e’ la prima e’ 1) e lo si molti plica per la base.

• Se c’e’ 0, si eleva solo al quadrato.

ES)

Calcolare :(7^11) mod 26 = ?

 

11 bin = 1011

1	[(1^2)*7]mod 26 = 7
0	(7*7)mod 26 = 23
1	(23^2)*7mod26= 11
1	(11^2)*7 mod26 = 15

Risposta: (7^11)mod26= 15

 

Inversione

Se (x*a) mod m = 1 , allora x= a^-1

x esiste se e solo se a e' perpendicolare ad m.

Se m =p, a^-1 esiste sempre.
 

 

Calcolo dell'inverso: Metodo di Lagrange (Metodo generale)

a^-1 = a^[φ(m)-1] mod m.

 

Calcolo dell'inverso: piccolo teorema di Fermat (Solo se m=p)

a^-1 = a ^p-2

ES)

m=p=3

a=7

7 ^-1 (mod 3) = 7 ^{(3 – 2)} (mod 3) = 7 (mod 3) = 1

Verifica: (7*1) mod 3 =1. [ok]

 

ES2)

m=p=15=3*5

a=7

φ(15) = 2*4 = 8

a^-1 = a ^ [φ(15)-1]= a^ 7 mod 15 = 7^7 mod 15 = 13

Verifica: (13*7) mod 15 = 1. [ok]

 

Elementi generatori

In un insieme Zp, gli elementi generatori A sono quelli appartenenti a Zp* tali che, detti i B gli elementi di Zp*, valga:

B= A^i , dove 0<=i<=p-2

Numero elementi generaltori = Funz.toziente(p-1).

 

Es)

m=p=5

A=2

|Z5|=5 |Z5*|=p-1=4

 

2^0 mod 5=1

2^1 mod 5 =2

2^2 mod 5=4

2^3 mod 5=3

 

Torna a inizio pagina