0:00:00.000,0:00:04.220
En los segmentos anteriores hablamos sobre inversión modular y dijimos que el algoritmo

0:00:04.220,0:00:08.238
de Euclides nos proporciona una forma eficiente de encontrar la inversa de un elemento módulo N

0:00:08.238,0:00:12.256
En este segmento iremos hacia adelante en el tiempo y nos moveremos al

0:00:12.256,0:00:15.866
siglo diecisiete y dieciocho donde hablaremos de

0:00:15.866,0:00:19.986
las contribuciones de Fermat y Euler. Antes de eso, hagamos una revisión rápida de

0:00:19.986,0:00:24.257
lo que discutimos en los segmentos previos. Como es usual voy a dejar que N denote el

0:00:24.257,0:00:28.427
entero positivo y sólo digamos que N es un entero de n-bits, en otras

0:00:28.427,0:00:32.445
palabras, es entre 2^n y 2^(n-1), como es usual vamos a dejar que P

0:00:32.445,0:00:36.761
denote un número primo. Ahora dijimos que ZN es un conjunto de enteros desde cero

0:00:36.761,0:00:41.370
a N-1 y dijimos que podemos sumar y multiplicar elementos en el conjunto módulo N.

0:00:41.370,0:00:46.186
También dijimos que ZN* es básicamente el conjunto de elementos invertibles en ZN. Y probamos

0:00:46.186,0:00:51.243
un simple lemma para decir que, X es inversible si y sólo si X es relativamente

0:00:51.243,0:00:55.879
primo a N. Y no sólo entendimos completamente qué elementos

0:00:55.879,0:01:00.635
son inversibles y cuáles no lo son, también mostramos un algoritmo muy eficiente basado en

0:01:00.635,0:01:05.572
el algoritmo extendido de Euclides, para buscar la inversa de un elemento X en ZN. Y dijimos

0:01:05.572,0:01:10.388
que el tiempo de ejecución de este algoritmo es básicamente del órden de n cuadrado, donde

0:01:10.388,0:01:16.107
nuevamente, n es el número de bits del número N mayúscula. Entonces, como dijimos, ahora

0:01:16.107,0:01:21.037
vamos a movernos de los tiempos de Grecia todo el camino hasta el siglo diceisiete y

0:01:21.037,0:01:26.276
hablaremos sobre Fermat. Fermat hizo un importante número de teoremas. El que quiero

0:01:26.276,0:01:31.206
mostrarles aquí hoy es el siguiente. Supongan que les doy un primo P. Entonces

0:01:31.206,0:01:36.260
de hecho para cualquier elemento X en ZP*, sucede que si miro a X y la elevo

0:01:36.260,0:01:41.130
a la potencia P-1 voy a obtener una, en ZP. Entonces tomemos un rápido ejemplo

0:01:41.130,0:01:46.061
Supongamos que P es igual a 5. Y busco 3 elevado a la

0:01:46.061,0:01:50.645
potencia P-1. En otras palabras, 3^4. Tres a la cuarta es 81

0:01:50.645,0:01:55.286
que de hecho, es uno módulo cinco. Este ejemplo satisface el teorema de Fermat.

0:01:55.286,0:01:59.521
Es interesante que Fermat de hecho no probó este teorema por sí mismo. La prueba

0:01:59.521,0:02:04.337
tuvo que esperar hasta Euler, que lo logró 100 años después.

0:02:04.337,0:02:09.122
Y de hecho, probó una visión mucho más general de este teorema. Veamos una

0:02:09.122,0:02:14.154
simple aplicación del teorema de Fermat. Supongamos que tomo un elemento X en ZP*

0:02:14.154,0:02:19.441
Y quiero recordarte aquí que P [inaudible] debe ser un primo. Bueno, entonces ¿qué

0:02:19.441,0:02:24.664
sabemos? Sabemos que X a la P-1 es igual a uno. Bueno, podemos escribir

0:02:24.664,0:02:29.573
x^(p-1) como x*x^(p-2). Bueno, entonces ahora sabemos que

0:02:29.573,0:02:34.087
x*x^(p-2) resulta ser 1. Y lo que eso

0:02:34.087,0:02:39.310
nos dice es que realmente la inversa de X modulo P, es simplemente x^(p-2).

0:02:39.310,0:02:44.042
Entonces esto nos otorga otro algoritmo para encontrar la inversa de X modulo un primo.

0:02:44.042,0:02:48.835
Simplemente elveamos X a la potencia de p - 2, y eso nos dará la inversa de X

0:02:48.835,0:02:53.508
Resulta ser que en realidad esto es una manera correcta de calcular inversas módulo un primo.

0:02:53.508,0:02:58.301
Pero tiene dos deficiencias comparado con el algoritmo de Euclides. Primero que todo, sólo

0:02:58.301,0:03:02.528
trabaja módulo primos, mientras que el algoritmo de Euclides trabaja módulo compuestos también