[Script Info]
Title: 
[Events]
Format: Layer, Start, End, Style, Name, MarginL, MarginR, MarginV, Effect, Text
Dialogue: 0,0:00:00.00,0:00:04.22,Default,,0000,0000,0000,,En los segmentos anteriores hablamos sobre inversión modular y dijimos que el algoritmo
Dialogue: 0,0:00:04.22,0:00:08.24,Default,,0000,0000,0000,,de Euclides nos proporciona una forma eficiente de encontrar la inversa de un elemento módulo N
Dialogue: 0,0:00:08.24,0:00:12.26,Default,,0000,0000,0000,,En este segmento iremos hacia adelante en el tiempo y nos moveremos al
Dialogue: 0,0:00:12.26,0:00:15.87,Default,,0000,0000,0000,,siglo diecisiete y dieciocho donde hablaremos de
Dialogue: 0,0:00:15.87,0:00:19.99,Default,,0000,0000,0000,,las contribuciones de Fermat y Euler. Antes de eso, hagamos una revisión rápida de
Dialogue: 0,0:00:19.99,0:00:24.26,Default,,0000,0000,0000,,lo que discutimos en los segmentos previos. Como es usual voy a dejar que N denote el
Dialogue: 0,0:00:24.26,0:00:28.43,Default,,0000,0000,0000,,entero positivo y sólo digamos que N es un entero de n-bits, en otras
Dialogue: 0,0:00:28.43,0:00:32.44,Default,,0000,0000,0000,,palabras, es entre 2^n y 2^(n-1), como es usual vamos a dejar que P
Dialogue: 0,0:00:32.44,0:00:36.76,Default,,0000,0000,0000,,denote un número primo. Ahora dijimos que ZN es un conjunto de enteros desde cero
Dialogue: 0,0:00:36.76,0:00:41.37,Default,,0000,0000,0000,,a N-1 y dijimos que podemos sumar y multiplicar elementos en el conjunto módulo N.
Dialogue: 0,0:00:41.37,0:00:46.19,Default,,0000,0000,0000,,También dijimos que ZN* es básicamente el conjunto de elementos invertibles en ZN. Y probamos
Dialogue: 0,0:00:46.19,0:00:51.24,Default,,0000,0000,0000,,un simple lemma para decir que, X es inversible si y sólo si X es relativamente
Dialogue: 0,0:00:51.24,0:00:55.88,Default,,0000,0000,0000,,primo a N. Y no sólo entendimos completamente qué elementos
Dialogue: 0,0:00:55.88,0:01:00.64,Default,,0000,0000,0000,,son inversibles y cuáles no lo son, también mostramos un algoritmo muy eficiente basado en
Dialogue: 0,0:01:00.64,0:01:05.57,Default,,0000,0000,0000,,el algoritmo extendido de Euclides, para buscar la inversa de un elemento X en ZN. Y dijimos
Dialogue: 0,0:01:05.57,0:01:10.39,Default,,0000,0000,0000,,que el tiempo de ejecución de este algoritmo es básicamente del órden de n cuadrado, donde
Dialogue: 0,0:01:10.39,0:01:16.11,Default,,0000,0000,0000,,nuevamente, n es el número de bits del número N mayúscula. Entonces, como dijimos, ahora
Dialogue: 0,0:01:16.11,0:01:21.04,Default,,0000,0000,0000,,vamos a movernos de los tiempos de Grecia todo el camino hasta el siglo diceisiete y
Dialogue: 0,0:01:21.04,0:01:26.28,Default,,0000,0000,0000,,hablaremos sobre Fermat. Fermat hizo un importante número de teoremas. El que quiero
Dialogue: 0,0:01:26.28,0:01:31.21,Default,,0000,0000,0000,,mostrarles aquí hoy es el siguiente. Supongan que les doy un primo P. Entonces
Dialogue: 0,0:01:31.21,0:01:36.26,Default,,0000,0000,0000,,de hecho para cualquier elemento X en ZP*, sucede que si miro a X y la elevo
Dialogue: 0,0:01:36.26,0:01:41.13,Default,,0000,0000,0000,,a la potencia P-1 voy a obtener una, en ZP. Entonces tomemos un rápido ejemplo
Dialogue: 0,0:01:41.13,0:01:46.06,Default,,0000,0000,0000,,Supongamos que P es igual a 5. Y busco 3 elevado a la
Dialogue: 0,0:01:46.06,0:01:50.64,Default,,0000,0000,0000,,potencia P-1. En otras palabras, 3^4. Tres a la cuarta es 81
Dialogue: 0,0:01:50.64,0:01:55.29,Default,,0000,0000,0000,,que de hecho, es uno módulo cinco. Este ejemplo satisface el teorema de Fermat.
Dialogue: 0,0:01:55.29,0:01:59.52,Default,,0000,0000,0000,,Es interesante que Fermat de hecho no probó este teorema por sí mismo. La prueba
Dialogue: 0,0:01:59.52,0:02:04.34,Default,,0000,0000,0000,,tuvo que esperar hasta Euler, que lo logró 100 años después.
Dialogue: 0,0:02:04.34,0:02:09.12,Default,,0000,0000,0000,,Y de hecho, probó una visión mucho más general de este teorema. Veamos una
Dialogue: 0,0:02:09.12,0:02:14.15,Default,,0000,0000,0000,,simple aplicación del teorema de Fermat. Supongamos que tomo un elemento X en ZP*
Dialogue: 0,0:02:14.15,0:02:19.44,Default,,0000,0000,0000,,Y quiero recordarte aquí que P [inaudible] debe ser un primo. Bueno, entonces ¿qué
Dialogue: 0,0:02:19.44,0:02:24.66,Default,,0000,0000,0000,,sabemos? Sabemos que X a la P-1 es igual a uno. Bueno, podemos escribir
Dialogue: 0,0:02:24.66,0:02:29.57,Default,,0000,0000,0000,,x^(p-1) como x*x^(p-2). Bueno, entonces ahora sabemos que
Dialogue: 0,0:02:29.57,0:02:34.09,Default,,0000,0000,0000,,x*x^(p-2) resulta ser 1. Y lo que eso
Dialogue: 0,0:02:34.09,0:02:39.31,Default,,0000,0000,0000,,nos dice es que realmente la inversa de X modulo P, es simplemente x^(p-2).
Dialogue: 0,0:02:39.31,0:02:44.04,Default,,0000,0000,0000,,Entonces esto nos otorga otro algoritmo para encontrar la inversa de X modulo un primo.
Dialogue: 0,0:02:44.04,0:02:48.84,Default,,0000,0000,0000,,Simplemente elveamos X a la potencia de p - 2, y eso nos dará la inversa de X
Dialogue: 0,0:02:48.84,0:02:53.51,Default,,0000,0000,0000,,Resulta ser que en realidad esto es una manera correcta de calcular inversas módulo un primo.
Dialogue: 0,0:02:53.51,0:02:58.30,Default,,0000,0000,0000,,Pero tiene dos deficiencias comparado con el algoritmo de Euclides. Primero que todo, sólo
Dialogue: 0,0:02:58.30,0:03:02.53,Default,,0000,0000,0000,,trabaja módulo primos, mientras que el algoritmo de Euclides trabaja módulo compuestos también