étant donné des entiers positifs où ** est une exponciation (par exemple dans Ruby, Python ou ^ dans certaines autres langues) et% est une opération de modulo. Quel est l'algorithme le plus efficace (avec la complexité Big-O la plus basse) pour le résoudre? Exemple: donné B = 5; c = 8; m = 13 Cet algorithme doit trouver E = 7 parce que 5 ** 7% 13 = 8 b, c, m où (b E tel que
6 Réponses :
de l'opérateur%, je suppose que vous travaillez avec des entiers.
Vous essayez de résoudre Le logarithme discret problème. Un algorithme raisonnable est Baby Step, étape géante , bien qu'il y en ait beaucoup d'autres, aucune dont sont particulièrement rapides.
La difficulté de trouver une solution rapide au problème du logarithme discret est une partie fondamentale de certains algorithmes cryptographiques populaires. Si vous trouvez une meilleure solution que l'une de ces personnes sur Wikipedia, faites-le moi savoir!
Enfer, s'il trouve un algorithme efficace vraiment , il a une chance équitable d'obtenir la médaille du champ
Ce n'est pas un simple problème du tout. Il s'appelle calculer le logarithme discret et c'est l'opération inverse à un Exponentation modulaire .
Il n'y a pas d'algorithme efficace connu. C'est-à-dire que n désigne le nombre de bits en m, tous les algorithmes connus fonctionnent dans O (2 ^ (n ^ c)) où C> 0.
Votre affirmation selon laquelle tous les algorithmes connus fonctionnent dans le temps O (C ^ N) pour certains C> 1 n'est pas correct. Il n'y a pas d'algorithme connu qui fonctionne dans du temps polynomial, mais il y a toujours des algorithmes connus sous-thérapeutiques.
Comme dit le problème général est difficile. Cependant, une façon pratique de trouver E Si et seulement si vous savez que E va être petite (comme dans votre exemple) serait juste d'essayer chaque e de 1.
BTW E == 3 est la première solution à votre exemple et vous pouvez évidemment trouver cela en 3 étapes, comparez-la à la résolution de la version non discrète et à la recherche naïvement de solutions entier, c'est-à-dire.
e = journal (c + n * m) / journal (b) où n est un entiteur non négatif
qui trouve E == 3 en 9 étapes
logarithme discret est un problème difficile
Computing Logarithmes distincts est considéré comme difficile. Non Méthode générale efficace pour calculer des logarithmes distincts sur Les ordinateurs classiques sont connus. P> blockQuote>
Je vais ajouter ici un simple algorithme bruteforce qui essaie toutes les valeurs possibles de
1 code> àm code> et émet une solution si elle a été trouvée. Notez qu'il peut y avoir plus d'une solution au problème ou à zéro solutions du tout. Cet algorithme vous retournera la plus petite valeur possible ou-1 code> s'il n'existe pas. P>xxx pré> et ici, vous pouvez voir que
3 code> est en fait la solution: p>print 5**3 % 13
Étant donné qu'un duplicatin de cette question a été demandé sous la balise Python, voici une implémentation de Python de Baby Step, une étape géante, qui, comme @ @markbeyers pointe, est une approche raisonnable (tant que le module n'est pas trop large): dans la mise en œuvre ci-dessus, un par exemple, si puis "pow (a, b, p)" évalue à 67385023448517 et Cela a pris environ 5 secondes sur ma machine. Pour l'exposant et le module de ces tailles, j'estime (basé sur des expériences de synchronisation) que la force brute aurait pris plusieurs mois. N peut être transmis au poisson pour un petit exposant même si p est cryptographique grand. Il trouvera l'exposant tant que l'exposant est inférieur à celui de n ** 2 . Lorsque n est omis, l'exposant sera toujours trouvé, mais pas nécessairement dans votre vie ou avec la mémoire de votre machine si p est trop grand.
Heureusement, symboly a Sydy est une bibliothèque Python pour les mathématiques symboliques. Il vise à devenir un système d'algèbre de l'ordinateur complet (CAS) tout en maintenant le code aussi simple que possible afin d'être compréhensible et facilement extensible. Sydy est entièrement écrit en Python. P>
blockQuote> Ceci est le Documentation sur le
discret_log code> fonction. Utilisez ceci pour importer: P> >>> discrete_log(41, 15, 7)
3