Crois le ou non, mais c'est pas si simple ton affaire.
Déjà la page wikipédia est pas franchement excellente, va plutôt voir ça qui est bien plus clair.
Ce qu'il faut comprendre c'est qu'on cherche x tel que a**x=b [mod n]. Un autre point, c'est que a**-m, ça veux dire en vrai inv_a**m [mod n] et que inv_a se définit par inv_a*a=1 [mod n] (voir ici et là).
Laissons les maths décanter un peu et voyons ton code.
Déjà, vire les while + incrément et utilise des for + range.
Ensuite, quand on dit 'hash table', il faut traduire dictionnaire en python, pas une liste.
Pour info, le but de l'algo c'est d'être plus rapide que du brut force en pré-calculant une partie du résultat. la table de hashage (dict) est utilisée pour accéder rapidement à ces pré-calculs, si on utilise une liste à reparcourir à chaque fois qu'on cherche dedans on perd tout l'intérêt de la manoeuvre.
Et comme je suis sympa, voilà comment je ferais :
def egcd(a, b):
""" r, u, v tq r = a*u + b*v et r = gcd(a, b)
source: https://fr.wikipedia.org/wiki/Algorithme_d%27Euclide_%C3%A9tendu
"""
r, u, v, r_, u_, v_ = a, 1, 0, b, 0, 1
while r_:
q = r / r_
r, u, v, r_, u_, v_ = (r_, u_, v_,
r-q*r_, u-q*u_, v-q*v_)
return r, u, v
def bsgs(n, a, b):
""" x tq pow(a, x, n) = b [mod n]
n: ordre
a: generateur
b: nb a inv
source: https://math.berkeley.edu/~sagrawal/su14_math55/notes_shank.pdf
"""
assert b % n
r, inva, _ = egcd(a, n)
assert r == 1
m = int(n ** .5) + 1
am = pow(inva, m, n)
table = {pow(a, j, n): j for j in range(m)}
Y = b
for i in range(m):
if Y in table:
return i * m + table[Y]
Y = (Y * am) % n
print 'fuck'
return 0
PS : Soit sympa, fais au moins l'effort de poser une question dans ton poste.
