Problem connecting to Twitter. Please try again.
Problem connecting to Twitter. Please try again.
Problem connecting to Twitter. Please try again.
Problem connecting to Twitter. Please try again.
Problem connecting to Twitter. Please try again.
El Problema del Logaritmo Discreto
-
0:02 - 0:06Necesitamos un procedimiento numérico que sea sencillo en un sentido
-
0:06 - 0:08y difícil en el otro.
-
0:08 - 0:13Esto nos lleva a la aritmética modular, también conocida como aritmética de reloj.
-
0:13 - 0:20Por ejemplo, para encontrar 46 mod 12, podemos coger una cuerda de longitud 46 unidades
-
0:20 - 0:25enrollarla alrededor de un reloj de 12 unidades denominado modulador,
-
0:25 - 0:28y donde la cuerda acabe está la solución.
-
0:28 - 0:33Así que decimos que 46 mod 12 es congruente con 10.
-
0:33 - 0:39Eso es fácil. Ahora, para hacerlo funcionar, usamos un modulador primo, por ejemplo 17.
-
0:39 - 0:44Entonces encontramos una raíz primitiva de 17, en este caso 3.
-
0:44 - 0:49Que tiene esta importante propiedad de que cuando se eleva a distintos exponentes
-
0:49 - 0:53la solución se distribuye uniformemente alrededor del reloj.
-
0:53 - 1:003 es conocido como el generador. Si elevamos 3 a cualquier exponente x
-
1:00 - 1:06la solución tiene las mismas probabilidades de ser un entero entre 0 y 17.
-
1:06 - 1:09Ahora, el procedimiento inverso es difícil.
-
1:09 - 1:14Esto es, partiendo de 12, encuentra el exponente al que 3 debe elevarse.
-
1:14 - 1:18Este problema es conocido como el problema del logaritmo discreto.
-
1:18 - 1:20Y ahora tenemos nuestra función unidireccional.
-
1:20 - 1:24Fácil de realizar, pero difícil de invertir.
-
1:24 - 1:30Dado 12, tendríamos que recurrir al método de ensayo y error para encontrar exponentes adecuados.
-
1:30 - 1:33¿Cómo de difícil es esto?
-
1:33 - 1:39Bueno, con números pequeños es fácil, pero si usamos un modulador con cientos de dígitos
-
1:39 - 1:42se vuelve imposible de resolver en la práctica.
-
1:42 - 1:47Incluso si tuvieras acceso a toda la potencia computacional de la toerra, te podría tomar miles de años
-
1:47 - 1:50recorrer todas las posibilidades.
-
1:50 - 1:54Por ello, la fortaleza de una función unidireccional parte del tiempo necesario para revertirla.
elezeta edited Spanish subtitles for Discrete Logarithm Problem |