Pierre De Fermat.docx

Pequeño teorema de Fermat

Luis Felipe Rincon Villegas Ingeniería de Sistemas y computación 3 semestre Recuperación de trabajo no presentado

Universidad del Quindío 24/05/2018

Pierre de Fermat Pierret de Fermat fue un aficionado a las matemáticas apodado el príncipe de los aficionados que gracias a la calidad de sus aportaciones y aunque el no lo deseaba logro un gran reconocimiento en el gremio de los amantes de los números, Fermat nació en una época de grandes matemáticos como Descartes, Leibniz, Newton, Jacobo y Juan Bernoulli, Galileo, Fermat se relacionaba con varios de estos matemáticos de primera fila y muchos descubrimientos de Fermat se conocieron gracias a cartas con acertijos que le enviaba a algunos de estos importantes matemáticos, en aquel entonces las matemáticas se empezaron a formar como una ciencia independiente Fermat contribuyó decisivamente a ello. Además del álgebra, la geometría analítica y el cálculo, otras ramas de la matemática empezaron a cultivarse en ese siglo: por ejemplo, la teoría de números y el cálculo de probabilidades. En teoría de números hay quien le considera el padre de la teoría de números moderna. En ese terreno, su famoso Gran Teorema le ha dado la fama universal de la cual era mucho más merecedor por sus contribuciones al álgebra, a la geometría y al cálculo.

El pequeño teorema de Fermat

Teorema:

Dos números naturales se llaman primos relativos si el máximo común divisor entre ellos es 1. Ejemplo: Los números 6 y 9 NO son primos relativos ya que los divisores de 6 son 1, 2, 3 y 6. Los divisores de 9 son 1, 3 y 9. Por lo tanto el máximo común divisor es 3. Los números 9 y 14 son primos relativos ya que los divisores de 9 son 1, 3 y 9, mientras que los divisores de 14 son 1, 2, 7 y 14. Por lo tanto el máximo común divisor es 1.

Aplicaciones del pequeño teorema de Fermat

En lo básico y común vemos aplicaciones para calcular residuos de números muy grandes que hacerlo de la forma normal nos llevaría un gran trabajo y tiempo, pero aplicando el pequeño teorema de Fermat anunciado anteriormente disminuye de gran manera la complejidad y el tiempo necesario para realizar este ejercicio, decidí pasar por alto estos ejemplos ya que son muy básicos. Pasando lo básico podemos ver las verdaderas utilidades que tiene en este teorema en sus aplicaciones en la primalidad y en criptografía.

Ejemplo: Test de primalidad Sistemas como el RSA se basan en que es muy difícil descomponer en factores primos a un número compuesto si este es muy grande, digamos, el producto de dos primos enormes. Pero, ¿cómo saber si un número es primo sin descomponerlo? Parecería que estamos frente a una dificultad equivalente a la que queremos poner a los posibles transgresores de la privacidad. Pues si el número p es del orden de las 200 cifras decimales, factorizarlo, con los métodos más veloces conocidos y las computadoras más poderosas es una tarea que lleva un tiempo enorme, si este fuera el criterio para saber si es primo un numero tardaríamos meses en armar una sola clave. Si ascendemos a 800 cifras decimales nos encontramos que esa tarea no puede realizarse, aunque para ello dispusiéramos del tiempo de vida del Sol. ¿Como superar entonces el escollo? Afortunadamente saber si un número es primo es más fácil que descomponer un numero en factores primos. Para chequear si un número es primo se dispone de herramientas que no implican factorizar el número. La más sencilla es haciendo uso del teorema de Fermat. Como se logra esto: El pequeño teorema de Fermat da una condición necesaria para que un número p sea primo. Es necesario que, para todo número natural a menor que p, ap-1 - 1 sea divisible por p, o sea, que ap-1 sea congruente con uno módulo p (en notación moderna como ap - 1 ≡ 1 (mod p)). Este principio es la base del test de primalidad de Fermat. Este test, al que asumimos una entrada n, consiste en ir probando que an-1 ≡ 1 (mod n) para una serie de valores de a, tales que sean menores que n. Si n es primo, entonces la congruencia se cumplirá siempre (condición necesaria del teorema) mientras que, si n es compuesto, la congruencia puede no cumplirse. Si

para algún valor de a (menor que n) no se cumple la congruencia, entonces n es compuesto. Una descripción de este test de forma general, en forma de algoritmo escrito en pseudocódigo, podría ser la siguiente:

Algoritmo Test de primalidad de Fermat. Entrada: Un número natural n>1, el número k de veces que se ejecuta el test y nos determina la fiabilidad del test.

1. Para j desde 1 hasta k haga lo siguiente: 2. A -Función genera un número aleatorio comprendido entre incluirlos)

y

3.Si a elevado (n-1) ¡≡ (no es congruente) 1(mod n) 3.1 Retorne compuesto 4-Retorne compuesto

Salida: COMPUESTO si n es compuesto y POSIBLE PRIMO si n es un posible primo.

(sin