WEBVTT

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

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

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

00:00:12.256 --> 00:00:15.866
siglo diecisiete y dieciocho donde hablaremos de

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

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

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

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

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

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

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

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

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

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

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

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

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

00:01:16.107 --> 00:01:21.037
vamos a movernos de los tiempos de Grecia todo el camino hasta el siglo diceisiete y

00:01:21.037 --> 00:01:26.276
hablaremos sobre Fermat. Fermat hizo un importante número de teoremas. El que quiero

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

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

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

00:01:41.130 --> 00:01:46.061
Supongamos que P es igual a 5. Y busco 3 elevado a la

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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