Logaritmo discreto

Da Wikipedia, l'enciclopedia libera.
(Reindirizzamento da Logaritmi discreti)
Vai alla navigazione Vai alla ricerca

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

[modifica | modifica wikitesto]

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:

.

Definiamo un'operazione che per convenienza qui denoteremo con su due numeri :

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

Definiamo perciò il "logaritmo discreto di un numero x in base a" come quel numero b tale che , cioè .

Il contesto in cui è forse più facile comprendere i logaritmi discreti è quello del gruppo moltiplicativo degli interi modulo p (con p numero primo), cioè l'insieme degli interi 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 ; per ottenere in questo gruppo, calcoliamo prima e dividiamo 81 per 17, ottenendo 4 con il resto di 13; perciò nel gruppo è .

Il logaritmo discreto è l'operazione inversa: dato , 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 è .

Definizione formale

[modifica | modifica wikitesto]

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 per un qualche intero k. Inoltre, se per due interi h e k, allora h e k sono congrui modulo n. Possiamo quindi definire una funzione:

dove indica l'anello degli interi modulo n, assegnando ad ogni 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:

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.

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 ; 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

[modifica | modifica wikitesto]

Collegamenti esterni

[modifica | modifica wikitesto]