algoritmo Pohlig-Hellman para el cálculo de logaritmos discretos

Question

Estoy trabajando en la codificación de la Pohlig-Hellman Algoritmo pero estoy teniendo un problema comprender los pasos en el algoritmo basado en la definición del algoritmo.

A juzgar por la Wiki de la algoritmo :

Sé que la primera parte 1) consiste en calcular el factor primordial de p-1 -. Que está muy bien

Sin embargo, no estoy seguro de lo que tengo que hacer en los pasos 2), donde se calcula el co-efficents:

Let x2 = c0 + c1(2). 
125(180/2) = 12590 1 mod (181) so c0 = 0.
125(180/4) = 12545 1 mod (181) so c1 = 0.
Thus, x2 = 0 + 0 = 0.

y 3) poner los coefficents juntos y resolver en el teorema del resto chino.

Alguien puede ayudar con la explicación de esto en la llanura Inglés (i) - o pseudocódigo. Quiero código de la solución, obviamente, a mí mismo, pero no puedo hacer ningún progreso más a menos entiendo el algoritmo.

Nota: He hecho un montón de búsqueda para esto y leer S. Pohlig y M. Hellman (1978). "Un algoritmo mejorado para el cálculo de logaritmos sobre GF (p) y su Importancia de cifrado, pero su todavía no realmente a tener sentido para mí.

Gracias de antemano

Actualización: ¿cómo es que q (125) se mantiene constante en este ejemplo .

Cuando, como en este ejemplo es aparece como que es el cálculo de una nueva q cada tiempo .

Para ser más específicos que no entiendo cómo se calcula la siguiente: Ahora divide 7531 por un ^ c0 para obtener 7531(a^-2) = 6735 mod p.

Answer 1

Empecemos con la idea principal detrás de Pohlig-Hellman. Supongamos que se nos da Y, G y P y que queremos encontrar x, tal que

  

y == g ^x (mod p).

(estoy usando == para denotar una relación de equivalencia). Para simplificar las cosas, también estoy suponiendo que el orden de g es p-1, es decir, el k positivo más pequeño con 1 == g ^k (mod p) es k = p-1.

Un método ineficaz para encontrar x, sería simplemente tratar todos los valores en el rango de 1 .. P-1. Algo mejor es la "Baby-paso gigante a paso" método que requiere O ( p ^0.5 ) operaciones aritméticas. Ambos métodos son bastante lento para grandes p. Pohlig-Hellman es una mejora significativa cuando p-1 tiene muchos factores. Es decir. asumir que

  

p-1 = n r

A continuación, lo Pohlig y Hellman proponen es resolver la ecuación

  

y ⁿ == (g ⁿ ) ^z   (Mod p).

Si tomamos logaritmos en base g en ambos lados, esto es lo mismo que

  

n log _g (y) == log _g (Y ⁿ ) == nz (mod p-1).

n se puede dividir a cabo, dando

  

log _g (y) == z (r mod).

Por lo tanto x == z (r mod).

Esta es una mejora, ya que sólo tenemos que buscar un rango de 0 .. r-1 para una solución de z. Y de nuevo "bebé-paso a paso gigante" se puede utilizar para mejorar la búsqueda de z. Obviamente, hacer esto una vez que aún no es una solución completa. Es decir. uno tiene que repetir el algoritmo anterior para cada factor primordial r de p-1 y después de usar el teorema chino del resto de encontrar x de las soluciones parciales. Esto funciona muy bien si p-1 es cuadrada libre.

Si p-1 es divisible por un poder primo, entonces una idea similar se puede utilizar. Por ejemplo supongamos que P-1 = m q ^k . En el primer paso, calculamos z tal que x == z (mod q) como se muestra anteriormente. Siguiente queremos extender esta a una solución x == z'(q mod ² ). P.ej. si p-1 = m q ² entonces esto significa que tenemos que encontrar z' de tal manera que

  

y ^m == (g ^m ) ^{z '} (mod p).

Desde ya sabemos que z '== z (mod q), z' debe estar en el conjunto {z, z + q, z + 2q, ..., z + (q-1) q}. Una vez más podríamos hacer ya sea una búsqueda exhaustiva para z' o mejorar la búsqueda con 'bebé-paso a paso gigante'. Este paso se repite para cada exponente de q, es de saber x mod q ⁱ iterativamente Derivar x mod q ^{i + 1} .

Answer 2

Estoy de codificación que yo mismo en este momento (JAVA). Estoy usando Pollard-Rho para encontrar los factores primos pequeños de p-1. Luego, utilizando Pohlig-Hellman para resolver una clave privada DSA. y = g ^ x. Estoy teniendo el mismo problema ..

ACTUALIZACIÓN: "Para ser más específicos que no entiendo cómo se calcula la siguiente:. Ahora divide 7531 por un ^ c0 para obtener 7531 (a ^ -2) = 6735 mod p"

si se encuentra el modInverse de un c0 ^ tendrá sentido

Regards