In crittografia si ricorre spesso all’utilizzo di problemi che sono supposti difficile (per i quali non sono noti algoritmi risolutivi in tempo polinomiale) per la costruzione di crittosistemi. In particolare, il problema del logaritmo discreto trova applicazione nella crittografia basata su curve ellittiche. Tra i diversi crittosistemi che si fondano sul problema del logaritmo discreto troviamo ElGamal (Taher Elgamal nel 1985).

Introduciamo brevemente il problema del logaritmo discreto: supponiamo di disporre della seguente equazione, b = a^x , conoscendo il valore delle variabili a e b potremmo facilmente ricavare il valore di x . Sappiamo infatti che: \log_{a}b = x . Tuttavia, se ci trovassimo davanti alla seguente equazione: b = a^x \pmod{p} , il processo risolutivo diventerebbe molto più complicato, anzi computazionalmente intrattabile.

Radice primitiva (generatore)

Prima di procedere oltre introduciamo la definizione di radice primitiva (o generatore): una radice primitiva è un intorno a tale che, a elevato a tutti i numeri dell’anello genera tutti i numeri dell’anello. Per maggiori informazioni circa la definizione di anello si veda la corrispondente pagina disponibile su: Wikipedia.it.