1
00:00:00,000 --> 00:00:04,220
En los segmentos anteriores hablamos sobre inversión modular y dijimos que el algoritmo

2
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

3
00:00:08,238 --> 00:00:12,256
En este segmento iremos hacia adelante en el tiempo y nos moveremos al

4
00:00:12,256 --> 00:00:15,866
siglo diecisiete y dieciocho donde hablaremos de

5
00:00:15,866 --> 00:00:19,986
las contribuciones de Fermat y Euler. Antes de eso, hagamos una revisión rápida de

6
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

7
00:00:24,257 --> 00:00:28,427
entero positivo y sólo digamos que N es un entero de n-bits, en otras

8
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

9
00:00:32,445 --> 00:00:36,761
denote un número primo. Ahora dijimos que ZN es un conjunto de enteros desde cero

10
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.

11
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

12
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

13
00:00:51,243 --> 00:00:55,879
primo a N. Y no sólo entendimos completamente qué elementos

14
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

15
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

16
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

17
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

18
00:01:16,107 --> 00:01:21,037
vamos a movernos de los tiempos de Grecia todo el camino hasta el siglo diceisiete y

19
00:01:21,037 --> 00:01:26,276
hablaremos sobre Fermat. Fermat hizo un importante número de teoremas. El que quiero

20
00:01:26,276 --> 00:01:31,206
mostrarles aquí hoy es el siguiente. Supongan que les doy un primo P. Entonces

21
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

22
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

23
00:01:41,130 --> 00:01:46,061
Supongamos que P es igual a 5. Y busco 3 elevado a la

24
00:01:46,061 --> 00:01:50,645
potencia P-1. En otras palabras, 3^4. Tres a la cuarta es 81

25
00:01:50,645 --> 00:01:55,286
que de hecho, es uno módulo cinco. Este ejemplo satisface el teorema de Fermat.

26
00:01:55,286 --> 00:01:59,521
Es interesante que Fermat de hecho no probó este teorema por sí mismo. La prueba

27
00:01:59,521 --> 00:02:04,337
tuvo que esperar hasta Euler, que lo logró 100 años después.

28
00:02:04,337 --> 00:02:09,122
Y de hecho, probó una visión mucho más general de este teorema. Veamos una

29
00:02:09,122 --> 00:02:14,154
simple aplicación del teorema de Fermat. Supongamos que tomo un elemento X en ZP*

30
00:02:14,154 --> 00:02:19,441
Y quiero recordarte aquí que P [inaudible] debe ser un primo. Bueno, entonces ¿qué

31
00:02:19,441 --> 00:02:24,664
sabemos? Sabemos que X a la P-1 es igual a uno. Bueno, podemos escribir

32
00:02:24,664 --> 00:02:29,573
x^(p-1) como x*x^(p-2). Bueno, entonces ahora sabemos que

33
00:02:29,573 --> 00:02:34,087
x*x^(p-2) resulta ser 1. Y lo que eso

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

35
00:02:39,310 --> 00:02:44,042
Entonces esto nos otorga otro algoritmo para encontrar la inversa de X modulo un primo.

36
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

37
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.

38
00:02:53,508 --> 00:02:58,301
Pero tiene dos deficiencias comparado con el algoritmo de Euclides. Primero que todo, sólo

39
00:02:58,301 --> 00:03:02,528
trabaja módulo primos, mientras que el algoritmo de Euclides trabaja módulo compuestos también