Logarithme discret

Le logarithme discret est un objet mathématique utilisé en cryptologie. Dans un groupe cyclique G fini engendré par α, le logarithme discret est l'application qui associe à un élément β du groupe G le plus petit entier naturel k tel que αk = β (la loi de groupe étant notée multiplicativement) définie sur les entiers. C'est donc une application réciproque de l'exponentiation k ↦ αk. C'est l'analogue du logarithme réel qui est la réciproque de l'exponentielle.

Le logarithme discret est utilisé pour la cryptographie à clé publique, typiquement dans l'échange de clés Diffie-Hellman et le chiffrement El Gamal. La raison est que, pour un certain nombre de groupes, on ne connait pas d'algorithme efficace pour le calcul du logarithme discret, alors que celui de la réciproque, l'exponentiation, se réalise en un nombre de multiplications logarithmique en la taille de l'argument (voir exponentiation rapide),