algorithme Pohlig-Hellman pour le calcul de logarithmes discrets

Question

Je travaille sur le codage du Pohlig-Hellman algorithme, mais je suis ayant problème à comprendre les étapes de l'algorithme basé sur la définition de l'algorithme.

Aller par le Wiki du algorithme :

Je sais que la première partie 1) est de calculer le facteur premier de p-1 -. Ce qui est bien

Cependant, je ne suis pas sûr de ce que je dois faire dans les étapes 2) où vous calculez les co-efficents:

Let x2 = c0 + c1(2). 
125(180/2) = 12590 1 mod (181) so c0 = 0.
125(180/4) = 12545 1 mod (181) so c1 = 0.
Thus, x2 = 0 + 0 = 0.

et 3) mettre les coefficents ensemble et résoudre dans le théorème du reste chinois.

Quelqu'un peut-il aider à expliquer cela en anglais ordinaire (i) - ou pseudo-code. Je veux coder la solution moi-même évidemment, mais je ne peux pas faire plus de progrès si je comprends l'algorithme.

Note: Je l'ai fait beaucoup de recherche pour cela, et je lis S. Pohlig et M. Hellman (1978). « Un algorithme amélioré pour l'informatique logarithmes sur GF (p) et son importance Cryptographic mais son pour me faire toujours pas vraiment de sens.

Merci d'avance

Mise à jour: comment se fait q (125) reste constante dans cet exemple .

Où comme dans cet exemple est apparaît comme il calcule une nouvelle q chaque temps .

Pour être plus précis, je ne comprends pas comment ce qui suit est calculé: Maintenant, divisez 7531 par un ^ c0 pour obtenir 7531(a^-2) = 6735 mod p.

Answer 1

Commençons par l'idée principale derrière Pohlig-Hellman. Supposons que nous donne y, g et p et que nous voulons trouver x, de sorte que

  

y == g ^x (mod p).

(j'utilise == pour désigner une relation d'équivalence). Pour simplifier les choses, je suppose aussi que l'ordre de g est p-1, à savoir l'est k = p-1 plus petit k positif avec 1 g == ^k (mod p).

Une méthode inefficace pour trouver x, serait d'essayer simplement toutes les valeurs dans la gamme 1 .. p-1. Un peu mieux est le qui nécessite O ( p ^0,5 ) des opérations arithmétiques. Les deux méthodes sont assez lentes pour les grandes p. Pohlig-Hellman est une amélioration significative lorsque p-1 a de nombreux facteurs. C'est à dire. supposer que

  

p-1 = n r

Alors qu'est-ce Pohlig et Hellman proposent est de résoudre l'équation

  

y ⁿ == (g ⁿ ) ^z   (Mod p).

Si l'on prend logarithmes à la g base des deux côtés, c'est le même que

  

n log _g (y) == log _g (y ⁿ ) == nz (p-1 mod).

n peut être divisé, donnant

  

log _g (y) == z (r mod).

D'où x == z (r mod).

Ceci est une amélioration, puisque nous avons seulement à la recherche d'une gamme 0 .. r-1 pour une solution de z. Et encore une fois « géant étape Baby-étape » peut être utilisé pour améliorer la recherche de z. De toute évidence, cette opération est une fois encore pas une solution complète. C'est à dire. on doit répéter l'algorithme ci-dessus pour chaque facteur premier r de p-1, puis d'utiliser le théorème chinois pour trouver x des solutions partielles. Cela fonctionne bien si p-1 est carré libre.

Si est divisible par une puissance prime peut alors être utilisé une idée similaire p-1. Par exemple, supposons que p-1 = m q ^k . Dans la première étape, on calcule z tel que x == z (mod q), comme illustré ci-dessus. Ensuite, nous voulons étendre à une solution x == z »(mod q ² ). Par exemple. si p-1 = m q ² cela signifie que nous devons trouver z » tel que

  

y ^m == (g ^m ) ^{z '} (mod p).

Puisque nous savons déjà que z '== z (mod q), z' doit être dans l'ensemble {z, z + q, z + 2q, ..., z + (q-1) q}. Encore une fois, nous pourrions soit faire une recherche exhaustive pour z » ou améliorer la recherche avec « géant étape baby-step ». Cette étape est répétée pour chaque exposant de q, c'est de savoir x mod q ⁱ nous dérivons itérativement x mod q ^{i + 1} .

Answer 2

Je suis coder moi-même en ce moment (JAVA). J'utilise Pollard-Rho pour trouver les petits facteurs premiers de p-1. Ensuite, en utilisant pour résoudre une clé privée DSA Pohlig-Hellman. y = g ^ x. Je suis le même problème ..

Mise à jour: "Pour être plus précis, je ne comprends pas comment ce qui suit est calculée: Maintenant, divisez 7531 par un ^ c0 pour obtenir 7531 (un ^ -2) = 6735 mod p."

si vous trouvez le modInverse d'un ^ c0 il sera logique

Cordialement