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.