Calcular logaritmo discreto

Question

Dadas enteros positivos b, c, m donde (b < m) is True que es encontrar un número entero positivo tal que e

(b**e % m == c) is True 

donde ** es exponenciación (por ejemplo, en Ruby, Python o^en algunos otros idiomas) y% es operación de módulo ¿Cuál es el algoritmo más efectivo (con la menor complejidad de O grande) para resolverlo?

Ejemplo:

Dada b = 5; c = 8; m = 13 este algoritmo debe encontrar e = 7 porque 5 ** 7% 13 = 8

Answer 1

Esto no es un problema simple en absoluto. Se llama calcular el discrete logarithm y es la operación inversa a modular exponentation.

No se conoce ningún algoritmo eficiente. 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.

Answer 2

Desde el operador% Supongo que está trabajando con números enteros.

Está tratando de resolver el problema the Discrete Logarithm. Un algoritmo razonable es Baby step, giant step, 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, por lo que si encuentra una solución mejor que cualquiera de los de Wikipedia, ¡hágamelo saber!

Answer 3

como dije el problema general es difícil. sin embargo, una forma práctica de encontrar e si y solo si usted sabe que e va a ser pequeño (como en su ejemplo) sería simplemente probar cada e de 1.

btw e == 3 es la primera solución para su ejemplo, y obviamente puede encontrar eso en 3 pasos, compare para resolver la versión no discreta, e ingenuamente buscando soluciones enteras, es decir,

e = log (c + n * m)/log (b) donde n es un no negativo número entero

que encuentra e == 3 en 9 pasos

Answer 4

Discrete logarithm es un problema difícil

Calcular logaritmos discretos se cree que es difícil. No se conoce el método general eficiente para calcular logaritmos discretos en computadoras convencionales.

voy a añadir aquí un algoritmo de fuerza bruta sencilla que trata cada valor posible 1-m y da salida a una solución si se encontró. Tenga en cuenta que puede haber más de una solución para el problema o cero soluciones en absoluto. Este algoritmo le devolverá el valor más pequeño posible o -1 si no existe.

def bruteLog(b, c, m): 
    s = 1 
    for i in xrange(m): 
     s = (s * b) % m 
     if s == c: 
      return i + 1 
    return -1 

print bruteLog(5, 8, 13) 

y aquí se puede ver que 3 es, de hecho, la solución:

print 5**3 % 13 

hay una mejor algoritmo, sino porque se le pide a menudo que se aplicará en las competiciones de programación, que se acaba de dar usted un enlace al explanation.

Answer 5

Dado que se hizo un duplicado de esta pregunta bajo la etiqueta de Python, aquí hay una implementación de Python paso a 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 la pesca de un pequeño exponente incluso si p es criptográficamente grande. Encontrará el exponente siempre que el exponente sea menor que N**2. Cuando se omite N, siempre se encontrará el exponente, pero no necesariamente durante su vida o con la memoria de su máquina si p es demasiado grande.

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 llevó unos 5 segundos en mi máquina. Para el exponente y el módulo de esos tamaños, estimo (en base a los experimentos de sincronización) que la fuerza bruta habría llevado varios meses.