Teorema fundamental de la aritmética: definición y uso en criptografía
El teorema fundamental de la aritmética (también llamado teorema de la factorización única) es un teorema básico de la teoría de los números. Afirma que todo número entero positivo mayor que 1 puede escribirse como un producto de números primos, y que esa descomposición es única salvo por el orden de los factores. Es decir, si un entero positivo n > 1 tiene dos descomposiciones en primos, los primos que aparecen en una son exactamente los mismos (con las mismas multiplicidades) que los de la otra, sólo puede variar el orden.
Por ejemplo:
6936 = 23 · 3 · 172
1200 = 24 · 3 · 52
La búsqueda de esos primos se llama factorización.
Esbozo de demostración
- Existencia. Se prueba por inducción fuerte o por el principio del mínimo contrajemplo: si n es compuesto, tiene un divisor a con 1 < a < n; por la hipótesis inductiva tanto a como n/a se factorizan en primos, luego n también.
- Unicidad. Se basa en el lema de Euclides: si p es primo y p divide a ab, entonces p divide a a o a b. A partir de ahí, si dos factorizaciones distintas existieran, se llega a una contradicción al comparar primos que dividen a uno y no al otro.
Consecuencias útiles
- Permite definir de forma sencilla operaciones aritméticas como el máximo común divisor (mcd) y el mínimo común múltiplo (mcm) a partir de las potencias de primos en cada número: tomar exponentes mínimos para el mcd y máximos para el mcm.
- Da estructura algebraica al anillo de enteros: Z es un dominio de factorización única (UFD, por sus siglas en inglés).
- Hace posible razonar sobre propiedades multiplicativas de funciones aritméticas (por ejemplo, la función totiente de Euler φ(n) puede calcularse a partir de la descomposición en primos).
Uso en criptografía
El teorema fundamental de la aritmética es parte del fundamento teórico que permiten ciertas técnicas criptográficas, especialmente las basadas en la dificultad computacional de factorizar enteros grandes.
- RSA como ejemplo. En RSA se genera un número n como producto de dos primos grandes p y q (un semiprimo). La clave pública contiene n y un exponente público e; la clave privada se obtiene usando p y q para calcular el inverso multiplicativo de e módulo φ(n). La seguridad de RSA depende de que, dado sólo n (pero sin conocer p y q), sea computacionalmente difícil factorizar n y así recuperar la clave privada.
- Dificultad práctica. Aunque la factorización es fácil para números pequeños, para enteros de cientos o miles de bits es muy costosa con los algoritmos conocidos. Por eso en criptografía se eligen primos grandes y se usan pruebas de primalidad y generadores de primos seguros.
- Algoritmos y medidas de seguridad. Existen métodos de factorización más eficientes que la división por prueba (por ejemplo, Pollard rho, el cribado cuadrático, y el algoritmo del cuerpo de números general —GNFS—). El coste de estos algoritmos guía el tamaño de las claves recomendadas (por ejemplo, 2048 bits o más para RSA en aplicaciones actuales).
En resumen, el teorema fundamental de la aritmética garantiza que toda estructura multiplicativa de los enteros se puede entender mediante primos, y esa propiedad combinada con la complejidad de factorizar números grandes es lo que hace posible (y seguro) cierto tipo de criptografía.
Prueba
La primera persona que demostró el teorema fue Euclides. La primera demostración detallada y correcta se encuentra en las Disquisitiones Arithmeticae de Carl Friedrich Gauß.
Algunas personas pueden pensar que el teorema es cierto en todas partes. Sin embargo, el teorema no es cierto en sistemas numéricos más generales, como los enteros algebraicos. Esto fue mencionado por primera vez por Ernst Kummer en 1843, en su trabajo sobre el último teorema de Fermat. Para más información al respecto: lea la teoría algebraica de los números.
La prueba consta de dos partes: en primer lugar, demostramos que todo número puede escribirse como producto de primos; en segundo lugar, demostramos que si escribimos un número como producto de primos por segunda vez, entonces las dos listas de números primos deben ser iguales.
Primera parte de la prueba
Demostramos que si no todo número mayor que 1 puede escribirse como producto de primos, terminamos en una especie de imposibilidad. Así que después concluimos que debe ser cierto que todo número puede escribirse como un producto de primos.
Así pues, veamos ahora qué ocurre cuando alguien dice que conoce un número entero positivo, mayor que 1, que no puede escribirse como producto de primos. En ese caso le pedimos que mencione todos los números, mayores que 1, que no pueden escribirse como producto de primos. Uno de estos números debe ser el más pequeño: llamémoslo n. Por supuesto, este número n no puede ser 1. Además, no puede ser un número primo, porque un número primo es un "producto" de un único primo: él mismo. Por tanto, debe ser un producto de números. Así pues,
n = ab
donde tanto a como b son enteros positivos que, por supuesto, son menores que n. Pero: n era el número más pequeño que no puede escribirse como producto de primos. Así que debe ser posible escribir a y b como productos de primos, porque ambos son menores que n. Pero entonces el producto
n = ab
también puede escribirse como un producto de primos. Esto es una imposibilidad porque hemos dicho que n no puede escribirse como producto de primos.
Ahora hemos demostrado la imposibilidad que existe si la primera parte del teorema no fuera cierta. De este modo, hemos demostrado la primera parte del teorema.
Segunda parte de la prueba
Ahora tenemos que demostrar que sólo hay una forma de escribir un número positivo mayor que 1 como producto de números primos.
Para ello, utilizamos el siguiente lema: si un número primo p divide a un producto ab, entonces divide a o divide a b (lema de Euclides). Primero demostramos este lema. Bien, supongamos ahora que p no divide a. Entonces p y a son coprimos y tenemos la identidad de Bezout que dice que debe haber enteros x e y tales que
px + ay = 1.
Multiplicando todo por b se obtiene
pbx + aby = b,
Recuerde que ab puede ser dividido por p. Así que ahora, en el lado izquierdo tenemos dos términos que son divisibles por p. Así que el término del lado derecho también es divisible por p. Ahora hemos demostrado que si p no divide a, debe dividir a b. Eso demuestra el lema.
Ahora demostraremos que podemos escribir un número entero mayor que 1 de una sola manera como producto de números primos. Tomemos dos productos de números primos A y B que tengan el mismo resultado. Así que sabemos para el resultado de los productos que A = B. Tomemos cualquier primo p del primer producto A. Divide a A, así que también divide a B. Utilizando varias veces el lema que acabamos de demostrar, podemos ver que p debe entonces dividir al menos un factor b de B. Pero los factores son todos primos en sí mismos, así que también b es primo. Pero sabemos que p también es primo, así que p debe ser igual a b. Así que ahora dividimos A por p y también dividimos B por p. Y obtenemos un resultado como A* = B*. De nuevo podemos tomar un primo p del primer producto A* y averiguar que es igual a algún número del producto B*. Siguiendo así, al final vemos que los factores primos de los dos productos deben ser exactamente iguales. Esto demuestra que podemos escribir un número entero positivo como un producto de primos de una sola manera.
Páginas relacionadas
- Teorema fundamental del álgebra
| Conjuntos de enteros basados en la divisibilidad | ||
| Resumen |
|
|
| Formas de factorización |
| |
| Sumas de divisores restringidas |
| |
| Con muchos divisores |
| |
| Relacionados con la secuencia de alícuotas |
| |
| ||
| Otros conjuntos |
| |
Preguntas y respuestas
P: ¿Qué es el Teorema Fundamental de la Aritmética?
R: El Teorema Fundamental de la Aritmética es un teorema de la teoría de los números que afirma que todo número entero positivo mayor que 1 puede escribirse como un producto de números primos, y que sólo hay una forma de escribir el número.
P: ¿Cómo se puede utilizar este teorema?
R: Este teorema puede utilizarse en criptografía.
P: ¿Qué ocurre si dos personas encuentran dos formas diferentes de escribir el mismo número?
R: Si dos personas encuentran dos formas diferentes de escribir el mismo número, lo único que puede ser diferente es el orden en que se escriben los primos.
P: ¿Qué es la factorización?
R: La factorización es encontrar todos los números primos que componen un número dado.
P: ¿Es el 6936 un ejemplo de número primo?
R: No, 6936 no es un número primo; se puede escribir como 23 - 3 - 172.
No, 6936 no es un número primo; se puede escribir como 23 - 3 - 172.
