Baby Schritt Giant Schritt Algorithmus für diskrete Log: falsche Giant Schritt

Question

Also ich versuche, den Baby Step Giant Step-Algorithmus zur Berechnung diskreter Protokolle zu implementieren. Unten ist mein Code:

# trying to solve 8576 = 3^x (mod 53047) 
p = 53047 
a = 3 
B = 8576 

m = int(math.ceil(math.sqrt(p-1))) 

baby = [] 
giant = [] 
for j in range(0,m-1): 
    baby.append((a**j)%p) 

for k in range(0,m-1): 
    val = a**(-1)%p 
    val2 = val**(k*m)%p 
    giant.append((B*val2)%p) 
    for i in xrange(len(baby)): 
     if giant[k] == baby[k]: 
      x = j + m*k 

Ich denke, es ist etwas falsch mit meinem riesigen Schritt ist, weil ich bin sehr kleine Werte als Ausgänge und keine Streichhölzer zu bekommen. Die richtige Antwort lautet x = 1234. Kann mir jemand sagen, was ich falsch mache?

Answer 1

Modulare Inverse werden nicht berechnet, indem reelle Inverswerte genommen werden und dann der Modulus des Ergebnisses genommen wird. Um die multiplikative Inverse von a mod p zu finden - müssen Sie eine Ganzzahlb mit ab = 1 (mod p) finden. Dies kann entweder durch den erweiterten euklidischen Algorithmus oder (als Abkürzung) von Fermats kleinen Satz mit:

a**(p-1) = 1 (mod p) 

Dies bedeutet, dass a**(p-2) (mod p)ist die Umkehrung von a.

Answer 2

# trying to solve 8576 = 3^x (mod 53047) 
p = 53047 
a = 3 
B = 8576 

P sollte immer> B wie könnte (a^x mod P = B und B> P) nehmen eine ein wieder zusehen es

beste Glück