Logaritmo discreto

Da Wikipedia, l'enciclopedia libera.

In matematica ed in particolare nell'algebra e nelle sue applicazioni i logaritmi discreti sono un analogo dei logaritmi ordinari per la teoria dei gruppi. Il problema del calcolo dei logaritmi discreti è simile a quello della fattorizzazione dei numeri interi, in quanto entrambi i problemi sono complessi (non sono noti algoritmi di soluzione efficienti), algoritmi dell'uno sono spesso adattati all'altro e entrambi sono stati utilizzati per costruire sistemi crittografici.

[modifica] Esempio

Il contesto in cui è forse più facile comprendere i logaritmi discreti è quello del gruppo moltiplicativo degli interi modulo p $\mathbb{Z}_p^*$ (con p numero primo). Questo gruppo può essere visto come l'insieme degli interi $\{1, \dots, p-1\}$ con l'operazione di moltiplicazione modulo p; cioè se vogliamo la potenza (matematica) k-esima di un elemento del gruppo possiamo calcolare la sua potenza k-esima come numero intero e poi prendere il resto della divisione per p. Questo processo è indicato come potenza discreta. Ad esempio, consideriamo $\mathbb{Z}_{17}^*$ ; per ottenere $34$ in questo gruppo, calcoliamo prima $34 = 81$ e dividiamo 81 per 17, ottenendo 4 con il resto di 13; perciò nel gruppo $\mathbb{Z}_{17}^*$ è $34 = 13$ .

Il logaritmo discreto è l'operazione inversa: dato $3^k \equiv 13 \mod 17$ , quale k rende l'espressione vera? A rigore ci sarebbero infinite soluzioni intere, per la natura modulare del problema; generalmente si cerca la più piccola soluzione non negativa, che è $k = 4$ .

[modifica] Definizione

In generale, sia G un gruppo ciclico finito di n elementi (supponiamo una scrittura moltiplicativa). Sia b un generatore di G; allora ogni elemento g di G può essere scritto nella forma $g = b k$ per un qualche intero k. Inoltre, se $b k = g = b h$ per due interi h e k, allora h e k sono congrui mudulo n. Possiamo quindi definire una funzione:

$\log_b:\ G\ \rightarrow\ \mathbb{Z}_n$

dove $\mathbb{Z}_n$ indica l'anello degli interi modulo n, assegnando ad ogni $g \in G$ la classe di congruenza k modulo n. Questa funzione è un isomorfismo tra gruppi, detto logaritmo discreto in base b. b è detta anche radice primitiva.

La formula per il cambio di base dei logaritmi ordinari rimane valida: se c è un altro generatore di G, si ha che:

$\log_c (g) = \log_c (b) \cdot \log_b (g)$

[modifica] Algoritmi

Non sono noti algoritmi efficienti per il calcolo dei logaritmi discreti. Un algoritmo possibile è quello di elevare b a potenze via via crescenti finché non si ottiene g; ciò funziona, ma richiede un tempo di calcolo lineare rispetto alla dimensione del gruppo G e quindi esponenziale rispetto al numero di cifre della dimesione del gruppo.

Esistono algoritmi più sofisticati, generalmente ispirati dai simili algoritmi per la fattorizzazione degli interi. Questi sono più veloci del precedente, ma nessuno è in tempo polinomiale.

Baby-step giant-step
algoritmo di rho Pollard per logaritmi
algoritmo di Pohlig-Hellman
Index calculus algorithm
Number field sieve
Function field sieve

[modifica] Crittografia

Il calcolo dei logaritmi discreti sembra un problema difficile (non sono noti algoritmi efficienti), mentre il problema inverso dell'esponenziazione discreta non lo è. Quest'asimmetria è analoga a quella fra la fattorizzazione di interi e la moltiplicazione di interi. Entrambe queste asimmetrie sono state utilizzate per la costruzione di sistemi crittografici.

Nella crittografia basata sui logaritmi discreti scelte comuni per il gruppo G sono i gruppi ciclici $\mathbb{Z}_p^*$ ; si veda Elgamal, Diffie-Hellman e Digital Signature Algorithm.

Le più recenti applicazioni della crittografia usano i logaritmi discreti in sottogruppi ciclici di curve ellettiche su campi finiti; si veda crittografia ellittica.

Estratto da "http://it.wikipedia.org../../../l/o/g/Logaritmo_discreto.html"

Categorie: Aritmetica modulare | Crittografia | Teoria dei gruppi | Teoria dei numeri