Solución:
Desde el operador%, supongo que está trabajando con números enteros.
Está intentando resolver el problema del logaritmo discreto. Un algoritmo razonable es Baby step, paso gigante, aunque hay muchos otros, ninguno de los cuales es particularmente rápido.
La dificultad de encontrar una solución rápida al problema del logaritmo discreto es una parte fundamental de algunos algoritmos criptográficos populares, así que si encuentra una solución mejor que cualquiera de las de Wikipedia, ¡hágamelo saber!
Este no es un problema simple en absoluto. Se llama calcular el logaritmo discreto y es la operación inversa a una exponencia modular.
No se conoce ningún algoritmo eficaz. Es decir, si N denota el número de bits en m, todos los algoritmos conocidos se ejecutan en O (2 ^ (N ^ C)) donde C> 0.
Dado que se hizo un duplicado de esta pregunta bajo la etiqueta de Python, aquí hay una implementación de Python de paso pequeño, paso gigante, que, como señala @MarkBeyers, es un enfoque razonable (siempre que el módulo no sea demasiado grande):
def baby_steps_giant_steps(a,b,p,N = None):
if not N: N = 1 + int(math.sqrt(p))
#initialize baby_steps table
baby_steps = {}
baby_step = 1
for r in range(N+1):
baby_steps[baby_step] = r
baby_step = baby_step * a % p
#now take the giant steps
giant_stride = pow(a,(p-2)*N,p)
giant_step = b
for q in range(N+1):
if giant_step in baby_steps:
return q*N + baby_steps[giant_step]
else:
giant_step = giant_step * giant_stride % p
return "No Match"
En la implementación anterior, un explícito N se puede pasar a pescar por un pequeño exponente incluso si p es criptográficamente grande. Encontrará el exponente siempre que el exponente sea menor que N**2. Cuando N se omite, el exponente siempre se encontrará, pero no necesariamente durante su vida o con la memoria de su máquina si p Es demasiado largo.
Por ejemplo, si
p = 70606432933607
a = 100001
b = 54696545758787
luego ‘pow (a, b, p)’ se evalúa como 67385023448517
y
>>> baby_steps_giant_steps(a,67385023448517,p)
54696545758787
Esto tardó unos 5 segundos en mi máquina. Para el exponente y el módulo de esos tamaños, estimo (basado en experimentos de tiempo) que la fuerza bruta habría tomado varios meses.