Ejercicio 1 - v)

Ejercicio 1 - v)

de Diego Cossio Lasalvia -
Número de respuestas: 3

Buenas noches como andan??

Estoy teniendo un problema con este ejercicio, los ejercicios los hice con python,

Utilizando el algoritmo antes desarrollado en el apartado 3, creo que logré destrancarme ya que estuve 2 días trancado, pero básicamente al final del código para verificar si el valor calculado es correcto lo que hago es 2^x = x_crt_calculado. 

Bueno pero mi duda no es está saben que si tomo p hasta con 70 bits el algoritmo en teoría termina, a partir de ahí empiezo a tener problema con la implementación al momento de calcular el ai, básicamente el xi calculado con el algoritmo de Pohlig & Hellman no se encuentra dentro del  H antes calculado.

Noc si alguien tuvo problema con esto ??

Y si podría tomar como valido hacerlo hasta 70 bits ??

Agradezco cualquier sugerencia.

Saludos





En respuesta a Diego Cossio Lasalvia

Re: Ejercicio 1 - v)

de Alfredo Viola -
Hola Diego:

La idea del problema es entender la descomposición del cálculo del logaritmo discreto usando el teorema chino del resto. Para esto, si p es primo se precisa que la decomposición de p-1 tenga sólo primos chicos como factores.

Si hiciste la parte iv) te habrás dado cuenta que precisas tener 2 o 3 primos chicos y elevarlos a potencias grandes y sumarle 1 y testear si este número es primo. Sino cambias las potencias e intentas de nuevo hasta hallar un número primo. Hay teoremas que te garantizan que este proceso lo podes hacer en tiempo esperado polinomial en la cantidad de bits de p.

Hallar el logaritmo discreto en conjuntos chicos (digamos 2, 3, 5, 7, 11, etc.) es trivial y NO precisas usar Pollard rho. Para grupos de tamaño q^r usas el algoritmo de Pohlig & Hellman.

La idea NO es "pelearse" con el software. Si podes usar sólo hasta 70 bits, hacelo hasta 70 bits. Lo fundamental es entender lo que está pasando. Lo explicás en el informe y seguis adelante. No hay problema. Pero es importante que indiques en el informe lo que pasó. Si hacés las cosas bien con 70 bits, vas a mostrar que entendiste el problema.

Ahora concentrate en el ejercicio 2 que no es trivial y vas a aprender muchas cosas importantes.

No se si contesté tu pregunta.

Saludos,

Tuba.
En respuesta a Diego Cossio Lasalvia

Re: Ejercicio 1 - v)

de Alfredo Viola -
Lo importante ahora es que te concentres en el ejercicio 2 que enseña muchos temas fundamentales, no sólo para el curso sino que fundamentalmente para tu trabajo profesional.

Saludos,
Tuba.