-
En los segmentos anteriores hablamos sobre inversión modular y dijimos que el algoritmo
-
de Euclides nos proporciona una forma eficiente de encontrar la inversa de un elemento módulo N
-
En este segmento iremos hacia adelante en el tiempo y nos moveremos al
-
siglo diecisiete y dieciocho donde hablaremos de
-
las contribuciones de Fermat y Euler. Antes de eso, hagamos una revisión rápida de
-
lo que discutimos en los segmentos previos. Como es usual voy a dejar que N denote el
-
entero positivo y sólo digamos que N es un entero de n-bits, en otras
-
palabras, es entre 2^n y 2^(n-1), como es usual vamos a dejar que P
-
denote un número primo. Ahora dijimos que ZN es un conjunto de enteros desde cero
-
a N-1 y dijimos que podemos sumar y multiplicar elementos en el conjunto módulo N.
-
También dijimos que ZN* es básicamente el conjunto de elementos invertibles en ZN. Y probamos
-
un simple lemma para decir que, X es inversible si y sólo si X es relativamente
-
primo a N. Y no sólo entendimos completamente qué elementos
-
son inversibles y cuáles no lo son, también mostramos un algoritmo muy eficiente basado en
-
el algoritmo extendido de Euclides, para buscar la inversa de un elemento X en ZN. Y dijimos
-
que el tiempo de ejecución de este algoritmo es básicamente del órden de n cuadrado, donde
-
nuevamente, n es el número de bits del número N mayúscula. Entonces, como dijimos, ahora
-
vamos a movernos de los tiempos de Grecia todo el camino hasta el siglo diceisiete y
-
hablaremos sobre Fermat. Fermat hizo un importante número de teoremas. El que quiero
-
mostrarles aquí hoy es el siguiente. Supongan que les doy un primo P. Entonces
-
de hecho para cualquier elemento X en ZP*, sucede que si miro a X y la elevo
-
a la potencia P-1 voy a obtener una, en ZP. Entonces tomemos un rápido ejemplo
-
Supongamos que P es igual a 5. Y busco 3 elevado a la
-
potencia P-1. En otras palabras, 3^4. Tres a la cuarta es 81
-
que de hecho, es uno módulo cinco. Este ejemplo satisface el teorema de Fermat.
-
Es interesante que Fermat de hecho no probó este teorema por sí mismo. La prueba
-
tuvo que esperar hasta Euler, que lo logró 100 años después.
-
Y de hecho, probó una visión mucho más general de este teorema. Veamos una
-
simple aplicación del teorema de Fermat. Supongamos que tomo un elemento X en ZP*
-
Y quiero recordarte aquí que P [inaudible] debe ser un primo. Bueno, entonces ¿qué
-
sabemos? Sabemos que X a la P-1 es igual a uno. Bueno, podemos escribir
-
x^(p-1) como x*x^(p-2). Bueno, entonces ahora sabemos que
-
x*x^(p-2) resulta ser 1. Y lo que eso
-
nos dice es que realmente la inversa de X modulo P, es simplemente x^(p-2).
-
Entonces esto nos otorga otro algoritmo para encontrar la inversa de X modulo un primo.
-
Simplemente elveamos X a la potencia de p - 2, y eso nos dará la inversa de X
-
Resulta ser que en realidad esto es una manera correcta de calcular inversas módulo un primo.
-
Pero tiene dos deficiencias comparado con el algoritmo de Euclides. Primero que todo, sólo
-
trabaja módulo primos, mientras que el algoritmo de Euclides trabaja módulo compuestos también
