Wie finden Sie einen Variablen Wert in der MOD-Ausdruck?

Question

9 = 2^X mod 11

Was ist X und wie finden Sie X?

Seine verwandten zu finden, der Klartext RSA-Algorithmus und ich Schreibe ein C-Programm für Sie.

Answer 1

Die Antwort ist 6 + 10i für jede ganze Zahl i.

Eine einfache Möglichkeit, Lösungen für kleine Module zu erhalten ist, alle Werte von x iterieren. Sie müssen nur zwischen 0 und 10 (= 11-1) überprüfen, um zu finden, die erste Lösung, wenn eine Lösung existiert

.

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

Ausgabe:

6
16
26
36
46

Offensichtlich wird dies eine lange Zeit in Anspruch nehmen, wenn die Modul groß ist.

Weitere Informationen finden Sie auf der diskreten Logarithmen Seite. Hinweis:

  

Kein effizienter klassischer Algorithmus für   Berechnen allgemeine diskrete Logarithmen   logbg ist bekannt. Der naive Algorithmus ist   b zu höhere und höhere Leistungen zu erhöhen   k, bis die gewünschte g gefunden wird; diese   manchmal genannt Versuch   Multiplikation. Dieser Algorithmus   erfordert Laufzeit linear in der   Größe der Gruppe G und damit   exponential in der Anzahl der Ziffern in   die Größe der Gruppe.

Wenn es einfach modular exponetiation zu invertieren, es wäre keine gute Verschlüsselungs primitiv sein.

Answer 2

Offensichtlich, die Folge des 2^n mod 11 werden zyklisch.

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

So, Zyklus-Länge ist die 10.

2^n mod 11 = 9 n=6+10*m, wobei m die ganze Zahl

Answer 3

ich denke, das gelöst werden kann unter Verwendung von modularer Arithmetik . Eine andere Möglichkeit ist die Berechnung 9 = 2 ^ X in F ₁₁ (Z / 11Z), aber das ist ein Teil der modularen Arithmetik, zu.

Eine andere Lösung (wo Sie nur eine Lösung finden) ist die Gleichung numerisch zu lösen, das ist wahrscheinlich einfacher, in einem C-Programm.