Comment trouver une valeur de variable dans une expression MOD?

Question

9 = 2 ^ X mod 11

Qu'est-ce que X et comment trouvez-vous X?

Il s’agit de trouver le texte brut dans l’algorithme RSA et j’écris un programme en langage C pour cela.

Answer 1

La réponse est 6 + 10i pour tout nombre entier i.

Un moyen simple d’obtenir des solutions pour les petits modules consiste à parcourir toutes les valeurs de x. Il suffit de vérifier entre 0 et 10 (= 11 - 1) pour trouver la première solution, le cas échéant.

x = 0
while x < 50:
    if 9 == 2**x % 11:
         print x
    x += 1

Sortie:

6
16
26
36
46

Évidemment, cela prendra beaucoup de temps si le module est grand.

Pour plus d'informations, consultez la page Logarithme discret . Remarque:

  

Pas d’algorithme classique efficace pour   calcul des logarithmes discrets généraux   logbg est connu. L'algorithme naïf est   élever b à des puissances de plus en plus élevées   k jusqu'à ce que le g souhaité soit trouvé; ce   est parfois appelé procès   multiplication. Cet algorithme   nécessite une durée linéaire dans le   la taille du groupe G et donc   exponentielle du nombre de chiffres de   la taille du groupe.

S'il était facile d'inverser l'exponétiation modulaire, ce ne serait pas une bonne primitive cryptographique.

Answer 2

Évidemment, la séquence de 2 ^ n mod 11 sera cyclique.

2 ^ 0 mod 11 = 1
2 ^ 1 mod 11 = 2
2 ^ 2 mod 11 = 4
2 ^ 3 mod 11 = 8
2 ^ 4 mod 11 = 5
2 ^ 5 mod 11 = 10
2 ^ 6 mod 11 = 9
2 ^ 7 mod 11 = 7
2 ^ 8 mod 11 = 3
2 ^ 9 mod 11 = 6
2 ^ 10 mod 11 = 1
2 ^ 11 mod 11 = 2

La durée du cycle est donc de 10.

2 ^ n mod 11 = 9 pour n = 6 + 10 * m où m est un entier

Answer 3

Je pense que cela peut être résolu à l'aide de l'arithmétique modulaire . Vous pouvez également calculer 9 = 2 ^ X dans F ₁₁ (Z / 11Z), mais cela fait également partie de l’arithmétique modulaire.

Une autre solution (où vous ne trouverez qu’UNE SEULE solution) consiste à résoudre l’équation numériquement, ce qui est probablement plus facile avec un programme C.