Algorithme de Pohlig-Hellman

En théorie des groupes , l' algorithme de Pohlig-Hellman , parfois appelé algorithme de Silver-Pohlig-Hellman , algorithme spécial pour le calcul de logarithmes discrets dans un groupe abélien fini dont l'ordre est un entier lisse .

L'algorithme a été introduit par Roland Silver, mais publié pour la première fois par Stephen Pohlig et Martin Hellman , qui attribuent à Silver sa découverte indépendante mais non publiée. Pohlig et Hellman citent également Richard Schroeppel et H. Block comme ayant trouvé le même algorithme, plus tard que Silver, mais encore une fois sans le publier.

L'algorithme de Pohlig-Hellman est un cas particulier important, utilisé comme sous-programme dans l'algorithme général (voir ci-dessous). Il s'applique aux groupes dont l'ordre est une puissance première . L'idée de base de cet algorithme est de calculer de manière itérative les chiffres -adiques du logarithme en « décalant » de manière répétée tous les chiffres inconnus de l'exposant, sauf un, et en calculant ce chiffre par des méthodes élémentaires.

(Notez que pour des raisons de lisibilité, l'algorithme est indiqué pour les groupes cycliques — en général, doit être remplacé par le sous-groupe généré par , qui est toujours cyclique.)

Entrée. Un groupe cyclique d'ordre avec générateur et un élément .

Sortie. L'entier unique tel que .

1. Initialiser
2. Calculer . D'après le théorème de Lagrange , cet élément a un ordre .
3. Pour tous , faites :
   1. Calculer . Par construction, l'ordre de cet élément doit diviser , donc .
   2. En utilisant l' algorithme baby-step-geant step , calculez de telle sorte que . Cela prend du temps .
   3. Ensemble .
4. Retour .

L'algorithme calcule les logarithmes discrets en termes de complexité temporelle , bien mieux que l' algorithme pas à pas géant lorsque celle-ci est grande.

Dans cette section, nous présentons le cas général de l'algorithme de Pohlig–Hellman. Les ingrédients de base sont l'algorithme de la section précédente (pour calculer un logarithme modulo chaque puissance première dans l'ordre du groupe) et le théorème du reste chinois (pour combiner ces éléments en un logarithme dans le groupe complet).

(Encore une fois, nous supposons que le groupe est cyclique, étant entendu qu'un groupe non cyclique doit être remplacé par le sous-groupe généré par l'élément de base du logarithme.)

Entrée. Un groupe cyclique d'ordre avec un générateur , un élément et une factorisation première .

Sortie. L'entier unique tel que .

1. Pour chaque , faites :
   1. Calculer . D'après le théorème de Lagrange , cet élément a un ordre .
   2. Calculer . Par construction, .
   3. En utilisant l'algorithme ci-dessus dans le groupe , calculez de telle sorte que .
2. Résoudre la congruence simultanée Le théorème du reste chinois garantit qu'il existe une solution unique .
3. Retour .

La correction de cet algorithme peut être vérifiée via la classification des groupes abéliens finis : L'élévation de et à la puissance de peut être comprise comme la projection sur le groupe de facteurs d'ordre .

L'entrée du pire cas pour l'algorithme de Pohlig–Hellman est un groupe d'ordre premier : Dans ce cas, il se dégrade en algorithme pas-à-pas-géant , donc la complexité temporelle du pire cas est . Cependant, il est beaucoup plus efficace si l'ordre est lisse : Plus précisément, si est la factorisation première de , alors la complexité de l'algorithme est opérations de groupe.