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