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