Logaritmo discreto

Template:F In matematica ed in particolare nell'algebra e nelle sue applicazioni i logaritmi discreti sono il corrispettivo dei logaritmi ordinari per l'aritmetica modulare.

Il problema del calcolo dei logaritmi discreti ha notevoli somiglianze con quello della fattorizzazione dei numeri interi, in quanto entrambi i problemi sono supposti difficili (non sono noti algoritmi che li risolvono in tempo polinomiale), algoritmi dell'uno sono spesso adattati all'altro e viceversa, ed entrambi sono stati utilizzati come base teorica per la costruzione di sistemi crittografici. In particolare, il logaritmo discreto trova applicazione nella crittografia basata su curve ellittiche. Tali sistemi crittografici fondano la propria sicurezza sulla supposta difficoltà di tali problemi.

Definizione informale

Così come il logaritmo è l'operazione inversa dell'esponenziale, alla stessa maniera il logaritmo discreto è l'operazione inversa della potenza discreta.

Si immagini di avere un insieme A contenente i numeri interi compresi fra 0 e p - 1, dove p è un numero primo:

$A=\{0,1,2,\dots ,p-1\}$.

Definiamo un'operazione che per convenienza qui denoteremo con $\otimes$ su due numeri $a,b\in A$:

$a\otimes b=a^{b}modp$

dove mod è l'operazione di modulo. Questa operazione $\otimes$ è la suddetta potenza discreta.

Definiamo perciò il "logaritmo discreto di un numero x in base a" come quel numero b tale che $a\otimes b=x$, cioè $a^{b}modp=x$.

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), cioè l'insieme degli interi $\{1,\dots ,p-1\}$ con l'operazione di moltiplicazione modulo p; quindi se vogliamo la potenza 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 $3^4$ in questo gruppo, calcoliamo prima $3^4=81$ e dividiamo 81 per 17, ottenendo 4 con il resto di 13; perciò nel gruppo ${\mathbb{Z}}_{17}^{*}$ è $3^4=13$.

Il logaritmo discreto è l'operazione inversa: dato $3^k\equiv 13mod17$, 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$.

Definizione formale

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 modulo n. Possiamo quindi definire una funzione:

${\log }_b:G\to {\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)$

Algoritmi

Non sono noti algoritmi efficienti per il calcolo dei logaritmi discreti. Un algoritmo possibile è la ricerca esaustiva, condotta elevando 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 dimensione del gruppo.

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

• Baby-step giant-step
• algoritmo rho di Pollard
• algoritmo di Pohlig-Hellman
• Index calculus algorithm
• Crivello dei campi di numeri generale
• Function field sieve

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 ellittiche su campi finiti; si veda crittografia ellittica.

Voci correlate

• Logaritmo
• Funzione unidirezionale

Collegamenti esterni

• Template:Collegamenti esterni